Stability Number and k-Hamiltonian [a, b]-factors

详细信息    查看全文

• 关键词：Graph ; Stability number ; Minimum degree ; k ; Hamiltonian graph ; k ; Hamiltonian \([a ; b]\) ; factor
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10156
• 期：1
• 页码：356-361
• 丛书名：Algorithms and Discrete Applied Mathematics
• ISBN：978-3-319-53007-9
• 卷排序：10156

文摘

Let a, b and k be three integers with \(b>a\ge 2\) and \(k\ge 0\), and let G be a graph. If \(G-U\) contains a Hamiltonian cycle for any \(U\subseteq V(G)\) with \(|U|=k\), then G is called a k-Hamiltonian graph. An [a, b]-factor F of a graph G is Hamiltonian if F admits a Hamiltonian cycle. If \(G-U\) includes a Hamiltonian [a, b]-factor for every subset \(U\subseteq V(G)\) with \(|U|=k\), then we say that G has a k-Hamiltonian [a, b]-factor. In this paper, we prove that if G is a k-Hamiltonian graph with $$ 1\le \alpha (G)\le \frac{4(b-2)(\delta (G)-a-k+1)}{(a+k+1)^{2}}, $$then G admits a k-Hamiltonian [a, b]-factor. Furthermore, it is shown that this result is sharp.KeywordsGraphStability numberMinimum degreek-Hamiltonian graphk-Hamiltonian \([a , b]\)-factorSupported by the National Natural Science Foundation of China (Grant Nos. 11371009, 11501256, 61503160) and the National Social Science Foundation of China (Grant No. 14AGL001) and the Natural Science Foundation of Xinjiang Province of China (Grant No. 2015211A003), and sponsored by 333 Project of Jiangsu Province.