Two forbidden subgraph pairs for Hamiltonicity of 3-connected graphs

DOI10.1007/S00373-012-1245-0MaRDI QIDQ2637726zbMATH OpenOpenAlexFDO

Authors Zhiquan Hu, Hou-yuan Lin

Publication date 14 February 2014

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-012-1245-0

zbMATH Keywords

claw-free graphsclosureforbidden subgraphsHamiltonicity

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Structural characterization of families of graphs (05C75)

Review text

Consider the problem of identifying the family of forbidden subgraphs that imply Hamiltonicity. Let \(N_{i,j,k}\) be the graph obtained by identifying end vertices of three disjoint paths of lengths \(i, j, k\) to the vertices of a triangle. The authors prove that every 3-connected claw-free and \(N_{i,7-i,2}\)-free graph is Hamiltonian. The result is shown to be sharp where \(i\), \(7-i\) and \(2\) in \(N_{i,7-i,2}\) are the largest integers.

Recommendations

• Four forbidden subgraph pairs for Hamiltonicity of 3-connected graphs
• Every 3-connected \(\{K_{1,3},N_{3,3,3}\}\)-free graph is Hamiltonian
• 3-connected \(\{K_{1,3},P_9\}\)-free graphs are Hamiltonian-connected
• Every 3-connected \(\{K_{1,3},N_{1,2,3}\}\)-free graph is Hamilton-connected
• scientific article; zbMATH DE number 1210918

Cites work

• A reduction method to find spanning Eulerian subgraphs
• Characterizing forbidden pairs for hamiltonian properties
• Claw-free 3-connectedP11-free graphs are hamiltonian
• Every 3-connected \(\{K_{1,3},N_{3,3,3}\}\)-free graph is Hamiltonian
• Every 3-connected claw-free \(Z_{8}\)-free graph is Hamiltonian
• Forbidden subgraphs and Hamiltonian properties and graphs
• Forbidden subgraphs for hamiltonicity of 3-connected claw-free graphs
• Forbidden subgraphs, hamiltonicity and closure in claw-free graphs
• Four forbidden subgraph pairs for Hamiltonicity of 3-connected graphs
• scientific article; zbMATH DE number 4191710 (Why is no real title available?)
• scientific article; zbMATH DE number 3730183 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• On a closure concept in claw-free graphs
• On Eulerian and Hamiltonian Graphs and Line Graphs
• Sufficient conditions for a graph to be Hamiltonian

Cited in

(19)

• Forbidden triples for Hamiltonicity
• Hamiltonian properties of 3-connected \{claw,hourglass\}-free graphs
• Every 3-connected \(\{ K_{1 , 3} , Z_7 \}\)-free graph of order at least 21 is Hamilton-connected
• Characterizing the difference between graph classes defined by forbidden pairs including the claw
• The local structure of claw-free graphs without induced generalized bulls
• A characterization of 2-connected \(\{ K_{1 , 3} , N_{3 , 1 , 1} \}\)-free non-Hamiltonian graphs
• Four forbidden subgraph pairs for Hamiltonicity of 3-connected graphs
• Every 3-connected \(\{K_{1,3},N_{1,2,3}\}\)-free graph is Hamilton-connected
• Hamiltonian property of 3-connected \([5,3]\)-graphs
• Pairs of forbidden class of subgraphs concerning K_1,3and P₆to have a cycle containing specified vertices
• Every 3-connected \(\{K_{1,3},N_{3,3,3}\}\)-free graph is Hamiltonian
• scientific article; zbMATH DE number 1210918 (Why is no real title available?)
• Forbidden triples implying Hamiltonicity: for all graphs
• Pairs of Heavy Subgraphs for Hamiltonicity of 2-Connected Graphs
• Forbidden subgraphs for hamiltonicity of 3-connected claw-free graphs
• Hamiltonicity and forbidden subgraphs in 4‐connected graphs
• Potential forbidden triples implying hamiltonicity: for sufficiently large graphs
• Forbidden pairs for traceability of 2-connected graphs
• Forbidden pairs for \(k\)-connected Hamiltonian graphs

This page was built for publication: Two forbidden subgraph pairs for Hamiltonicity of 3-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2637726)