Hamiltonian cycles in tough (P2 ∪ P3)-free graphs
Hamiltonian cycles in tough (P2 ∪ P3)-free graphs
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Songling Shan
中科院分区：
文献类型：
--
作者：
Songling Shan
设t > 0为真实的数，G为图.我们说G是t-坚韧的，如果对于G的每一个割集S，|S| G− S的分量数至少为t。确定任意图的韧性是一个NP-难问题。Chvátal的韧性猜想，即存在一个常数t0使得每个至少有三个顶点的t0坚韧图是Hamilton图，在一般情况下仍然是开放的。一个图被称为（P2 <$P3）-free，如果它不包含任何同构于P2 <$P3的导出子图，P2 <$P3是两个分别为2阶和3阶的顶点不相交路的并集。本文证明了每一个至少有三个顶点的15-坚韧（P2 ∪ P3）-自由图都是汉密尔顿图。数学科目分类：05 C38
Let t > 0 be a real number and 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. Determining toughness is an NP-hard problem for arbitrary graphs. The Toughness Conjecture of Chvátal, stating that there exists a constant t0 such that every t0tough graph with at least three vertices is hamiltonian, is still open in general. A graph is called (P2∪P3)-free if it does not contain any induced subgraph isomorphic to P2 ∪ P3, the union of two vertex-disjoint paths of order 2 and 3, respectively. In this paper, we show that every 15-tough (P2 ∪ P3)-free graph with at least three vertices is hamiltonian. Mathematics Subject Classifications: 05C38