An Ore-type condition for Hamiltonicity in tough graphs

DOI10.37236/10389zbMATH Open1485.05098arXiv2103.05146OpenAlexW4210574511MaRDI QIDQ2073293FDOQ2073293

Authors: Songling Shan 

Publication date: 1 February 2022

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

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.

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

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

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 Keywords

Ore's theorem[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Chv%EF%BF%BD%EF%BF%BDtal%27s+toughness+conjecture&go=Go Chv��tal's toughness conjecture]toughness of a graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Hamiltonian degree conditions for tough graphs
• Title not available (Why is that?)
• Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs
• On the 1-fault Hamiltonicity for graphs satisfying Ore's theorem
• Title not available (Why is that?)
• An Ore-type condition for hamiltonicity in tough graphs and the extremal examples
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• Toughness, Hamiltonicity and spectral radius in graphs

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)