A note on hamiltonian cycles in 4-tough (P2 ∪ kP1)-free graphs
A note on hamiltonian cycles in 4-tough (P2 ∪ kP1)-free graphs
复制标题
关于 4-tough (P2 → kP1)-free 图中的哈密顿循环的注释
DOI：
10.1016/j.disc.2022.113081
复制
发表时间：
2022-12
影响因子：
0.8
通讯作者：
Songling Shan
中科院分区：
文献类型：
--
作者：
Lingjuan Shi;Songling Shan
设t是实数，G是一个图。我们说G是t -tough如果对于G的每一个切集S， | S |与G−S的分量数之比至少是t。Chvátal的韧性猜想，指出存在一个常数t0，使得每一个至少有三个顶点的t0韧性图都是哈密顿的，一般来说仍然是开放的。对于任意给定的整数k≥1，如果图G不包含p2与k个孤立顶点的不相交并作为诱导子图，则图G是（p2∪k p1）自由的。在这篇笔记中，我们证明了每一个至少有三个顶点的4-坚韧且2k连通（p2∪k1）自由图都是哈密顿图。这个结果在某种意义上是经典Chvátal-Erdős定理的“扩展”，即每个至少有三个顶点的max （2, k）连通（k + 1） p1自由图都是哈密顿的。
Let t > 0 be a real number and let G be a graph. We say G is t -tough if for every cutset S of G , the ratio of | S | to the number of components of G − S is at least t . The Toughness Conjecture of Chvátal, stating that there exists a constant t 0 such that every t 0 -tough graph with at least three vertices is hamiltonian, is still open in general. For any given integer k ≥ 1 , a graph G is ( P 2 ∪ k P 1 ) free if G does not contain the disjoint union of P 2 and k isolated vertices as an induced subgraph. In this note, we show that every 4-tough and 2 k -connected ( P 2 ∪ k P 1 ) -free graph with at least three vertices is hamiltonian. This result in some sense is an “extension” of the classical Chvátal-Erdős Theorem that every max { 2 , k } -connected ( k + 1 ) P 1 -free graph on at least three vertices is hamiltonian.
登录
查看更多内容
DOI：
10.1016/s0166-218x(99)00141-9
发表时间：
2000-02
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
D. Bauer;H. Broersma;H. J. Veldman
通讯作者：
D. Bauer;H. Broersma;H. J. Veldman
影响因子：
0.9
作者：
H. Broersma;V. Patel;A. Pyatkin
通讯作者：
H. Broersma;V. Patel;A. Pyatkin
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Songling Shan
通讯作者：
Songling Shan
影响因子：
0.9
作者：
Songling Shan
通讯作者：
Songling Shan
影响因子：
0.7
作者：
H. Broersma;Binlong Li;Shenggui Zhang
通讯作者：
H. Broersma;Binlong Li;Shenggui Zhang