|
|||||
|
|
The 2-extendability of 5-connected graphs on surfaces with large representativity |
|
| Authors: | Ken-ichi Kawarabayashi |
| Institution: | a National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan b Faculty of Education and Human Sciences, Yokohama National University, 79-2 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan c Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA d Tsuruoka National College of Technology, Tsuruoka, Yamagata 997-8511, Japan |
| Abstract: | A graph with at least 2k+2 vertices is said to be k-extendable if any independent set of k edges in it extends to a perfect matching. We shall show that every 5-connected graph G of even order embedded on a closed surface F2, except the sphere, is 2-extendable if ρ(G)?7−2χ(F2), where ρ(G) stands for the representativity of G on F2 and χ(F2) for the Euler characteristic of F2. |
| Keywords: | Matching Surface Genus Representativity |
| 本文献已被 ScienceDirect 等数据库收录！ | |