|
|||||
|
|
The 2-Extendability of Graphs on the Projective Plane, the Torus and the Klein Bottle |
|
| Authors: | Iwao Mizukai Seiya Negami Yusuke Suzuki |
| Institution: | 1. Graduate School of Department of Information Media and Environment Sciences, Yokohama National University, 79-7 Tokiwadai, Hodogaya-Ku, Yokohama, 240-8501, Japan 2. Faculty of Education and Human Sciences, Yokohama National University, 79-7 Tokiwadai, Hodogaya-Ku, Yokohama, 240-8501, Japan 3. 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. We shall show that every 5-connected graph of even order embedded on the projective plane and every 6-connected one embedded on the torus and the Klein bottle is 2-extendable and characterize the forbidden structures for 5-connected toroidal graphs to be 2-extendable. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |