Hamiltonian cycles in $ 15 $-tough ($ P_{3}\cup 3P_{1} $)-free graphs
Hamiltonian cycles in $ 15 $-tough ($ P_{3}\cup 3P_{1} $)-free graphs
A graph $ G $ is called $ t $-tough if $ \left|S\right|\geq t\cdot w\left(G-S\right)$ for every cutset $ S $ of $G$. Chv\'atal conjectured that there exists a constant $ t_{0} $ such that every $ t_{0} $-tough graph has a hamiltonian cycle. Gao and Shan have proved that every $7$-tough $(P_{3}\cup 2P_{1})$-free grah is hamiltonian. In this paper, we confirm this conjecture for $ (P_{3}\cup 3P_{1}) $-free graphs.
Hui Ma、Lili Hao、Weihua Yang
数学
Hui Ma,Lili Hao,Weihua Yang.Hamiltonian cycles in $ 15 $-tough ($ P_{3}\cup 3P_{1} $)-free graphs[EB/OL].(2025-05-07)[2025-07-01].https://arxiv.org/abs/2505.04189.点此复制
评论