原图是平面图的4-连通线图的哈密尔顿连通性（英文）

详细信息    查看全文 | 推荐本文 |

英文篇名：Hamiltonicity of 4-connected Line Graph of a Planar Graph 作者：王茂群 ; 杨卫华 英文作者：WANG Maoqun;YANG Weihua;College of Mathematics, Taiyuan University of Technology; 关键词：哈密尔顿连通 ; 线图 ; 平面图 ; 2-哈密尔顿 英文关键词：Hamiltonian-connected;;line graph;;planar graph;;2-Hamiltonian 中文刊名：SXJZ 英文刊名：Advances in Mathematics 机构：太原理工大学数学学院; 出版日期：2019-01-15 出版单位：数学进展 年：2019 期：v.48 基金：supported by NSFC (No.11671296) 语种：英文; 页：SXJZ201901003 页数：6 CN：01 ISSN：11-2312/O1 分类号：31-36

摘要

对于一个整数.s≥0,如果图G的任何一个点子集S (?) V(G)满足|S|≤s,并且G-S是哈密尔顿的,那么称图G是s-哈密尔顿的.本文证明原图是平面图的4-连通线图是2-哈密尔顿的并且还是哈密尔顿连通的.这一结果推广了赖虹建在[Graph and Combinatorics,1994, 10:249-253]中的结果.
        For an integer s > 0, a graph G is s-Hamiltonian if for any vertex subset S CV(G) with |S| ≤ s, G-S is Hamiltonian. In this note, we show that every 4-connected line graph of a planar graph is 2-Hamiltonian, and it is also Hamiltonian-connected. These results generalize work of Lai in [Graph and Combinatorics, 1994, 10: 249-253]

引文

[1] Bondy, J.A. and Murty, U.S.R., Graph Theory with Applications, New York:Elsevier, 1976.
    [2] Broersma, H.J. and Veldman, H.J., 3-connected line graphs of triangular graphs are panconnected and1-Hamiltonian, J. Graph Theory, 1987, 11(3):399-407.
    [3] Kaiser, T., Vrána, P., Hamilton cycles in 5-connected line graphs, European J. Combin., 2012, 33:924-947.
    [4] Kriesell, M., All 4-connected line graphs of claw-free graphs are Hamiltonian-connected, J. Combin. Theory Ser. B, 2001, 82:306-315.
    [5] Lai, H.J., Every 4-connected line graph of a planar graph is Hamiltonian, Graph and Combinatorics, 1994,10:249-253.
    [6] Lai, H.J. and Shao, Y., On s-Hamiltonian line graphs, J. Graph Theory, 2013, 74:344-358.
    [7] Lai, H.J., Shao, Y. and Zhan, S., Every 4-connected line graph of a quasi claw-free graph is Hamiltonian connected, Discrete Math., 2008, 308:5312-5316.
    [8] Lesniak-Foster, L., On n-Hamiltonian line graphs, J. Combin. Theory Ser. B, 1977, 22:263-273.
    [9] Thomas, R. and Yu, X.X., 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser.B, 1994, 62:114-132.
    [10] Thomassen, C., A theorem on paths in planar graphs, J. Graph Theory, 1983, 7:169-176.
    [11] Thomassen, C., Reflections on graph theory, J. Graph Theory, 1986, 10:309-323.
    [12] Tutte, W.T., A theorem on planar graphs, Trans. Amer. Math. Soc., 1956, 82:99-116.