Equimatchable Graphs on Surfaces

Investor logo

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

EIBEN Eduard KOTRBČÍK Michal

Year of publication 2016
Type Article in Periodical
Magazine / Source Journal of Graph Theory
MU Faculty or unit

Faculty of Informatics

Citation
Web http://dx.doi.org/10.1002/jgt.21859
Doi http://dx.doi.org/10.1002/jgt.21859
Field Informatics
Keywords graph; matching; equimatchable; factor-critical; embedding; genus; bipartite; degeneracy
Description 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) U {v}) is either K_{2n} 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\sqrt{g} + 17 if g <= 2 and to 12\sqrt{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\sqrt{2g} vertices, which establishes that the maximum size of such graphs is \Theta(\sqrt{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 4d + 1 vertices, where a graph is d-degenerate if every its induced subgraph contains a vertex of degree at most d.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info