首页 | 本学科首页   官方微博 | 高级检索  
     


Hamiltonian connectedness in 3-connected line graphs
Authors:Hong-Jian Lai  Gexin Yu
Affiliation:a Department of Mathematics, West Virginia University, Morgantown, WV 26506, United States
b Arts and Science, Ohio University Southern, Ironton, OH 45638, United States
c Department of Mathematics, Vanderbilt University, Nashville, TN 37240, United States
d Department of Mathematics, Millersville University, Millersville, PA 17551, United States
Abstract:
We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K5E(C4), where C4 is an cycle of length 4 in K5) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.
Keywords:Hamiltonian connected   Collapsible graphs   Core graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号