On Toughness and Hamiltonicity of 2K2‐Free Graphs
On Toughness and Hamiltonicity of 2K2‐Free Graphs
复制标题
DOI：
10.1002/jgt.21734
复制
发表时间：
2014-03
影响因子：
0.9
通讯作者：
H. Broersma;V. Patel;A. Pyatkin
中科院分区：
文献类型：
--
作者：
H. Broersma;V. Patel;A. Pyatkin
（不完全）图 G 的韧性是 t 的最小值，其中存在顶点切割 A，其去除产生 |A|/t 分量。对于一般输入图来说，确定韧性是一个 NP 难题。 Chvátal 的韧性猜想指出，存在一个常数 t，使得至少三个顶点上的韧性至少为 t 的每个图都是哈密顿图，该猜想对于一般图仍然是开放的。我们将分割图的一些已知韧性结果扩展到更一般的 2K2-free 图类，即不包含两个顶点不相交边作为诱导子图的图。我们证明了确定韧性的问题是多项式可解的，并且 Chvátal 的韧性猜想对于 2K2 无图是成立的。
The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields |A|/t components. Determining toughness is an NP‐hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K2‐free graphs, that is, graphs that do not contain two vertex‐disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K2‐free graphs.