An Ore-type condition for Hamiltonicity in tough graphs

DOI10.37236/10389zbMATH Open1485.05098OpenAlexW4210574511MaRDI QIDQ2073293FDOQ2073293

Authors Songling Shan

Publication date 1 February 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.05146

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Ore's theoremtoughness of a graphChvátal's toughness conjecture

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Abstract: Let $G$ be a $t$-tough graph on $nge3$ vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of $G$ is greater than $fracnt+1-1$, then $G$ is hamiltonian. In terms of Ore-type hamiltonicity conditions, the problem was only studied when $t$ is between 1 and 2. In this paper, we show that if the degree sum of any two nonadjacent vertices of $G$ is greater than $frac2nt+1+t-2$, then $G$ is hamiltonian.

Recommendations

• scientific article; zbMATH DE number 861334
• A sufficient condition for Hamiltonian cycles in tough graphs
• Hamiltonian degree conditions for tough graphs
• scientific article; zbMATH DE number 434902
• scientific article; zbMATH DE number 4177107

Cites work

• Existence of Dlambda-cycles and Dlambda-paths
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• Long cycles in graphs with large degree sums
• Long cycles in graphs with prescribed toughness and minimum degree
• Not every 2-tough graph is Hamiltonian
• Note on Hamilton Circuits
• On Maximal Circuits in Finite Graphs
• Some Theorems on Abstract Graphs
• Tough graphs and Hamiltonian circuits.
• Toughness in graphs -- a survey

Cited in

(9)

• Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs
• Toughness, Hamiltonicity and spectral radius in graphs
• scientific article; zbMATH DE number 861334 (Why is no real title available?)
• An Ore-type condition for hamiltonicity in tough graphs and the extremal examples
• A closure lemma for tough graphs and Hamiltonian degree conditions
• scientific article; zbMATH DE number 4177107 (Why is no real title available?)
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• Hamiltonian degree conditions for tough graphs
• On the 1-fault Hamiltonicity for graphs satisfying Ore's theorem

This page was built for publication: An Ore-type condition for Hamiltonicity in tough graphs

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