Equimatchable Graphs on Surfaces. Issue 1 (28th January 2015)

• Record Type: Journal Article
• Authors: Eiben, Eduard; Kotrbčík, Michal
• Is Part Of: Journal of graph theory. Volume 81:Issue 1(2016)
• Page Start: 35
• Page End: 49
• Publication Date: 2015-01-28
• Subjects: graph -- matching -- equimatchable -- factor‐critical -- embedding -- genus -- bipartite -- degeneracy -- 05C70 -- 05C10 -- 05C35; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21859
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A graph G is equimatchable if each matching in G is a subset of a maximum‐size matching and it is factor critical if G − v has a perfect matching for each vertex v of G . It is known that any 2‐connected equimatchable graph is either bipartite or factor critical. We prove that for 2‐connected factor‐critical equimatchable graph G the graph G ∖ ( V ( M ) ∪ { v } ) is either K 2 n or K n, n for some n for any vertex v of G and any minimal matching M such that { v } is a component of G ∖ V ( M ) . We use this result to improve the upper bounds on the maximum number of vertices of 2‐connected equimatchable factor‐critical graphs embeddable in the orientable surface of genus g to 4 g + 17 if g ≤ 2 and to 12 g + 5 if g ≥ 3 . Moreover, for any nonnegative integer g we construct a 2‐connected equimatchable factor‐critical graph with genus g and more than 4 2 g vertices, which establishes that the maximum size of such graphs is Θ ( g ) . Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers g, h, and k we provide a construction of arbitrarily large 2‐connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face‐width k . Finally, we prove that any d ‐degenerate 2‐connected equimatchable factor‐critical graph has at most 4 d + 1 vertices, where a graph is d ‐degenerate if every its induced subgraph contains a vertex of degree at most d .