On 3-stable number conditions in -connected claw-free graphs |
| |
Authors: | Zheng Yan Masao Tsugaki |
| |
Affiliation: | 1. Institute of Applied Mathematics, Yangtzeu University, Jingzhou, PR China;2. Tokyo University of Science, Tokyo, Japan |
| |
Abstract: | For a subgraph of , let be the maximum number of vertices of that are pairwise distance at least three in . In this paper, we prove three theorems. Let be a positive integer, and let be a subgraph of an -connected claw-free graph . We prove that if , then either can be covered by a cycle in , or there exists a cycle in such that . This result generalizes the result of Broersma and Lu that has a cycle covering all the vertices of if . We also prove that if , then either can be covered by a path in , or there exists a path in such that . By using the second result, we prove the third result. For a tree , a vertex of with degree one is called a leaf of . For an integer , a tree which has at most leaves is called a -ended tree. We prove that if , then has a -ended tree covering all the vertices of . This result gives a positive answer to the conjecture proposed by Kano et al. (2012). |
| |
Keywords: | Claw-free Independence number K-ended tree Stable set Hamiltonian cycle Connectivity |
本文献已被 ScienceDirect 等数据库收录! |
|