Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902881 | Discrete Mathematics | 2018 | 9 Pages |
Abstract
For a subgraph X of G, let αG3(X) be the maximum number of vertices of X that are pairwise distance at least three in G. In this paper, we prove three theorems. Let n be a positive integer, and let H be a subgraph of an n-connected claw-free graph G. We prove that if nâ¥2, then either H can be covered by a cycle in G, or there exists a cycle C in G such that αG3(HâV(C))â¤Î±G3(H)ân. This result generalizes the result of Broersma and Lu that G has a cycle covering all the vertices of H if αG3(H)â¤n. We also prove that if nâ¥1, then either H can be covered by a path in G, or there exists a path P in G such that αG3(HâV(P))â¤Î±G3(H)ânâ1. By using the second result, we prove the third result. For a tree T, a vertex of T with degree one is called a leaf of T. For an integer kâ¥2, a tree which has at most k leaves is called a k-ended tree. We prove that if αG3(H)â¤n+kâ1, then G has a k-ended tree covering all the vertices of H. This result gives a positive answer to the conjecture proposed by Kano et al. (2012).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zheng Yan, Masao Tsugaki,