Equimatchable Graphs on Surfaces |
| |
| Authors: | Eduard Eiben Michal Kotrbčík |
| |
| Affiliation: | 1. INSTITUTE OF INFORMATION SYSTEMS, VIENNA UNIVERSITY OF TECHNOLOGY (TU WIEN), FAVORITENSTRA?E 9‐11, AUSTRIA;2. DEPARTMENT OF COMPUTER SCIENCE, FACULTY OF INFORMATICS, MASARYK UNIVERSITY, CZECH REPUBLIC |
| |
| 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  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  is either  or  for some n for any vertex v of G and any minimal matching M such that  is a component of  . 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  if  and to  if  . Moreover, for any nonnegative integer g we construct a 2‐connected equimatchable factor‐critical graph with genus g and more than  vertices, which establishes that the maximum size of such graphs is  . 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  vertices, where a graph is d‐degenerate if every its induced subgraph contains a vertex of degree at most d. |
| |
| Keywords: | graph matching equimatchable factor‐critical embedding genus bipartite degeneracy 05C70 05C10 05C35 |
|
|
