Bounding the Size of Equimatchable Graphs of Fixed Genus |
| |
Authors: | Ken-ichi Kawarabayashi Michael D Plummer |
| |
Institution: | (1) National Institute of Informatics, 2 - 1 - 2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan;(2) Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA |
| |
Abstract: | A graph G is said to be equimatchable if every matching in G extends to (i.e., is a subset of) a maximum matching in G. In an earlier paper with Saito, the authors showed that there are only a finite number of 3-connected equimatchable planar
graphs. In the present paper, this result is extended by showing that in a surface of any fixed genus (orientable or non-orientable),
there are only a finite number of 3-connected equimatchable graphs having a minimal embedding of representativity at least
three. (In fact, if the graphs considered are non-bipartite, the representativity three hypothesis may be dropped.) The proof
makes use of the Gallai-Edmonds decomposition theorem for matchings.
|
| |
Keywords: | Embedded graph Genus Matching Equimatchable Surface |
本文献已被 SpringerLink 等数据库收录! |
|