TY - JOUR
T1 - Hamiltonicity of 3-connected line graphs
AU - Yang, Weihua
AU - Xiong, Liming
AU - Lai, Hongjian
AU - Guo, Xiaofeng
PY - 2012/11
Y1 - 2012/11
N2 - Thomassen conjectured that every 4-connected line graph is Hamiltonian. Lai et al. conjectured [H. 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] that every 3-connected, essentially 4-connected line graph is Hamiltonian. In this note, we first show that the conjecture posed by Lai et al. is not true and there is an infinite family of counterexamples; we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is Hamiltonian; examples show that all conditions are sharp.
AB - Thomassen conjectured that every 4-connected line graph is Hamiltonian. Lai et al. conjectured [H. 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] that every 3-connected, essentially 4-connected line graph is Hamiltonian. In this note, we first show that the conjecture posed by Lai et al. is not true and there is an infinite family of counterexamples; we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is Hamiltonian; examples show that all conditions are sharp.
KW - Collapsible graph Hamiltonian graph
KW - Dominating
KW - Eulerian subgraph
KW - Line graph
KW - Super-Eulerian graphs
KW - Thomassen's conjecture
UR - http://www.scopus.com/inward/record.url?scp=84865648137&partnerID=8YFLogxK
U2 - 10.1016/j.aml.2012.02.032
DO - 10.1016/j.aml.2012.02.032
M3 - Article
AN - SCOPUS:84865648137
SN - 0893-9659
VL - 25
SP - 1835
EP - 1838
JO - Applied Mathematics Letters
JF - Applied Mathematics Letters
IS - 11
ER -