کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902881 1632395 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On 3-stable number conditions in n-connected claw-free graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On 3-stable number conditions in n-connected claw-free graphs
چکیده انگلیسی
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).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 9, September 2018, Pages 2499-2507
نویسندگان
, ,