An Ore-type condition for Hamiltonicity in tough graphs

Songling Shan¹

¹Illinois State University

The electronic journal of combinatorics, Tome 29 (2022) no. 1

Résumé

Let $G$ be a $t$-tough graph on $n\geqslant 3$ vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of $G$ is greater than $\frac{n}{t+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 $\frac{2n}{t+1}+t-2$, then $G$ is hamiltonian. A corrigendum was added to this paper on March 23, 2022.

Détail

DOI : 10.37236/10389

Classification : 05C45, 05C38
Mots-clés : Ore's theorem, toughness of a graph, Chvátal's toughness conjecture