Equimatchable Graphs on Surfaces

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

EIBEN Eduard KOTRBČÍK Michal

Rok publikování 2016
Druh Článek v odborném periodiku
Časopis / Zdroj Journal of Graph Theory
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://dx.doi.org/10.1002/jgt.21859
Doi http://dx.doi.org/10.1002/jgt.21859
Obor Informatika
Klíčová slova graph; matching; equimatchable; factor-critical; embedding; genus; bipartite; degeneracy
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.