|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Director of Academic Committee at Kaifa District
其他任职：开发区校区学术分委员会主任（Director of Academic Committee at Kaifa Campus）
性别：男
毕业院校：多伦多大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：软件工程. 运筹学与控制论
办公地点：开发区（Kaifa District Campus）
联系方式：mingchul@dlut.edu.cn
电子邮箱：mingchul@dlut.edu.cn
Hamiltonian Connectedness in 4-Connected Hourglass-free Claw-free Graphs
点击次数：
论文类型：期刊论文
发表时间：2011-12-01
发表刊物：JOURNAL OF GRAPH THEORY
收录刊物：Scopus、SCIE、EI
卷号：68
期号：4
页面范围：285-298
ISSN号：0364-9024
关键字：Hamiltonian connectedness; claw-free; hourglass-free
摘要：An hourglass is the only graph with degree sequence 4,2,2,2,2 (i.e. two triangles meeting in exactly one vertex). There are infinitely many claw-free graphs G such that G is not hamiltonian connected while its Ryjacek closure cl(G) is hamiltonian connected. This raises such a problem what conditions can guarantee that a claw-free graph G is hamiltonian connected if and only if cl(G) is hamiltonian connected. In this paper, we will do exploration toward the direction, and show that a 3-connected {claw, (P(6))(2), hourglass}-free graph G with minimum degree at least 4 is hamiltonian connected if and only if cl(G) is hamiltonian connected, where (P6) 2 is the square of a path P6 on 6 vertices. Using the result, we prove that every 4-connected {claw, (P6) 2, hourglass}-free graph is hamiltonian connected, hereby generalizing the result that every 4-connected hourglass-free line graph is hamiltonian connected by Kriesell [J Combinatorial Theory (B) 82 (2001), 306-315]. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68: 285-298, 2011