Two forbidden subgraph pairs for Hamiltonicity of 3-connected graphs (Q2637726)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two forbidden subgraph pairs for Hamiltonicity of 3-connected graphs |
scientific article |
Statements
Two forbidden subgraph pairs for Hamiltonicity of 3-connected graphs (English)
0 references
14 February 2014
0 references
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.
0 references
Hamiltonicity
0 references
forbidden subgraphs
0 references
claw-free graphs
0 references
closure
0 references