TY - JOUR
T1 - Hamiltonian properties of 3-connected {claw,hourglass}-free graphs
AU - Ryjáček, Zdeněk
AU - Vrána, Petr
AU - Xiong, Liming
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2018/6
Y1 - 2018/6
N2 - We show that some sufficient conditions for hamiltonian properties of claw-free graphs can be substantially strengthened under an additional assumption that G is hourglass-free (where hourglass is the graph with degree sequence 4,2,2,2,2). Let G be a 3-connected claw-free and hourglass-free graph of order n. We show that (i) if G is P20-free, Z18-free, or N2i,2j,2k-free with i+j+k≤9, then G is hamiltonian,(ii) if G is P12-free, then G is Hamilton-connected,(iii) G contains a cycle of length at least min{σ12(G),n}, unless L−1(cl(G)) has a nontrivial contraction to the Petersen graph,(iv) if σ13(G)≥n+1, then G is hamiltonian, unless L−1(cl(G)) has a nontrivial contraction to the Petersen graph. Here Pi denotes the path on i vertices, Zi (Ni,j,k) denotes the graph obtained by attaching a path of length i≥1 (three vertex-disjoint paths of lengths i,j,k≥1) to a triangle, σk(G) denotes the minimum degree sum over all independent sets of size k, and L−1(cl(G)) is the line graph preimage of the closure of G.
AB - We show that some sufficient conditions for hamiltonian properties of claw-free graphs can be substantially strengthened under an additional assumption that G is hourglass-free (where hourglass is the graph with degree sequence 4,2,2,2,2). Let G be a 3-connected claw-free and hourglass-free graph of order n. We show that (i) if G is P20-free, Z18-free, or N2i,2j,2k-free with i+j+k≤9, then G is hamiltonian,(ii) if G is P12-free, then G is Hamilton-connected,(iii) G contains a cycle of length at least min{σ12(G),n}, unless L−1(cl(G)) has a nontrivial contraction to the Petersen graph,(iv) if σ13(G)≥n+1, then G is hamiltonian, unless L−1(cl(G)) has a nontrivial contraction to the Petersen graph. Here Pi denotes the path on i vertices, Zi (Ni,j,k) denotes the graph obtained by attaching a path of length i≥1 (three vertex-disjoint paths of lengths i,j,k≥1) to a triangle, σk(G) denotes the minimum degree sum over all independent sets of size k, and L−1(cl(G)) is the line graph preimage of the closure of G.
KW - Circumference
KW - Claw-free
KW - Degree condition
KW - Forbidden subgraph
KW - Hamilton-connected
KW - Hamiltonian
KW - Hourglass-free
UR - http://www.scopus.com/inward/record.url?scp=85034661325&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2017.10.033
DO - 10.1016/j.disc.2017.10.033
M3 - Article
AN - SCOPUS:85034661325
SN - 0012-365X
VL - 341
SP - 1806
EP - 1815
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 6
ER -