The 2-extendability of 5-connected graphs on the Klein bottle |
| |
Authors: | Seiya Negami |
| |
Institution: | a Faculty of Education and Human Sciences, Yokohama National University, 79-7 Taokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japanb Tsuruoka National College of Technology, Tsuruoka, Yamagata 997-8511, Japan |
| |
Abstract: | A graph is said to be k-extendable if any independent set of k edges extends to a perfect matching. In this paper, we shall characterize the forbidden structures for 5-connected graphs on the Klein bottle to be 2-extendable. This fact also gives us a sharp lower bound of representativity of 5-connected graphs embedded on the Klein bottle to have such a property, which was considered in Kawarabayashi et al. (submitted for publication) 4]. |
| |
Keywords: | Matching Extendability The Klein bottle |
本文献已被 ScienceDirect 等数据库收录! |
|