Hamiltonicity of 3-connected line graphs

Weihua Yang; Liming Xiong; Hongjian Lai; Xiaofeng Guo

doi:10.1016/j.aml.2012.02.032

Hamiltonicity of 3-connected line graphs

Weihua Yang^*, Liming Xiong, Hongjian Lai, Xiaofeng Guo

^*此作品的通讯作者

数学学院

科研成果: 期刊稿件 › 文章 › 同行评审

4 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	1835-1838
页数	4
期刊	Applied Mathematics Letters
卷	25
期	11
DOI	https://doi.org/10.1016/j.aml.2012.02.032
出版状态	已出版 - 11月 2012

访问文件

10.1016/j.aml.2012.02.032

其它文件与链接

链接到 Scopus 的出版物

引用此

Yang, W., Xiong, L., Lai, H., & Guo, X. (2012). Hamiltonicity of 3-connected line graphs. Applied Mathematics Letters, 25(11), 1835-1838. https://doi.org/10.1016/j.aml.2012.02.032

@article{788c699452214674a912a70e6dc5b44b,

title = "Hamiltonicity of 3-connected line graphs",

abstract = "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.",

keywords = "Collapsible graph Hamiltonian graph, Dominating, Eulerian subgraph, Line graph, Super-Eulerian graphs, Thomassen's conjecture",

author = "Weihua Yang and Liming Xiong and Hongjian Lai and Xiaofeng Guo",

year = "2012",

month = nov,

doi = "10.1016/j.aml.2012.02.032",

language = "English",

volume = "25",

pages = "1835--1838",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

publisher = "Elsevier Ltd.",

number = "11",

}

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 -

Hamiltonicity of 3-connected line graphs

摘要

访问文件

其它文件与链接

指纹

引用此