Collapsible graphs and Hamiltonian connectedness of line graphs
Collapsible graphs and Hamiltonian connectedness of line graphs
复制标题
DOI：
10.1016/j.dam.2012.03.028
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
Weihua Yang;H. Lai;Hao Li;Xiaofeng Guo
中科院分区：
文献类型：
--
作者：
Weihua Yang;H. Lai;Hao Li;Xiaofeng Guo
托马森猜想，每个4连通的线图都是哈密顿的。Chen和Lai[Z.-H.Chen，H.-J.Lai，Reducing Technologies for Super-Eulerian Groups and Related-A Up，in：Ku Toong-Hsin(主编)，Combinatorics and Graph They，Vol.95，World Science，新加坡/London，1995，pp.53-69，Conjection 8.6]猜想，每个3边连通的、本质上是6边连通的图都是可折叠的。在本文中，我们证明了以下结果。(1)每个边度至少为7的3-边连通、本质6-边连通图是可折叠的。(2)每个边度至少为6且至多24个3度顶点的3-边连通、本质5-边连通图是可折叠的，这意味着一个最多24个3度顶点的图的最小度至少为6的5-连通线图是哈密顿图。(3)每个3-连通、本质11-连通的线图都是哈密顿连通的，这加强了[H.-J.Lai，Y.Shao，H.Wu，J.周，每个3-连通，本质11-连通的线图都是哈密尔顿的，J.Combin。理论，爵士。B 96(2006)571-576]，作者Lai等人。(4)用与詹其雄不同的方法证明了7-连通线图是哈密顿连通的，利用Ryjáček和Vrána提出的多重图闭包，在保持无爪图的哈密顿连通性的前提下，将结果(3)和(4)推广到无爪图。
Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai [Z.-H. Chen, H.-J. Lai, Reduction techniques for super-Eulerian graphs and related topics—an update, in: Ku Tung-Hsin (Ed.), Combinatorics and Graph Theory, vol. 95, World Scientific, Singapore/London, 1995, pp. 53–69, Conjecture 8.6] conjectured that every 3-edge connected, essentially 6-edge connected graph is collapsible. In this paper, we prove the following results. (1) Every 3-edge connected, essentially 6-edge connected graph with edge-degree at least 7 is collapsible. (2) Every 3-edge connected, essentially 5-edge connected graph with edge-degree at least 6 and at most 24 vertices of degree 3 is collapsible which implies that 5-connected line graph with minimum degree at least 6 of a graph with at most 24 vertices of degree 3 is Hamiltonian. (3) Every 3-connected, essentially 11-connected line graph is Hamilton-connected which strengthens the result in [H.-J. Lai, Y. Shao, H. Wu, J. Zhou, Every 3-connected, essentially 11-connected line graph is Hamiltonian, J. Combin. Theory, Ser. B 96 (2006) 571–576] by Lai et al. (4) Every 7-connected line graph is Hamiltonian connected which is proved by a method different from Zhan’s. By using the multigraph closure introduced by Ryjáček and Vrána which turns a claw-free graph into the line graph of a multigraph while preserving its Hamilton-connectedness, the results (3) and (4) can be extended to claw-free graphs.