A Closure Lemma for tough graphs and Hamiltonian degree conditions

Abstract

The closure of a graph $G$ is the graph $G^{\ast }$ obtained from $G$ by repeatedly adding edges between pairs of non-adjacent vertices whose degree sum is at least $n$, where $n$ is the number of vertices of $G$. The well-known Closure Lemma proved by Bondy and Chvátal states that a graph $G$ is Hamiltonian if and only if its closure $G^{\ast }$ is. This lemma can be used to prove several classical results in Hamiltonian graph theory. We prove a version of the Closure Lemma for tough graphs. A graph $G$ is $t$-tough if for any set $S$ of vertices of $G$, the number of components of $G-S$ is at most $t|S|$. A Hamiltonian graph must necessarily be 1-tough. Conversely, Chvátal conjectured that there exists a constant $t$ such that every $t$-tough graph is Hamiltonian. The {\it $t$-closure} of a graph $G$ is the graph $G^{t\ast }$ obtained from $G$ by repeatedly adding edges between pairs of non-adjacent vertices whose degree sum is at least $n-t$. We prove that, for $t\ge 2$, a $\frac{3t-1}{2}$-tough graph $G$ is Hamiltonian if and only if its $t$-closure $G^{t\ast }$ is. Hoàng conjectured the following: Let $G$ be a graph with degree sequence $d_1\le d_2\le \dots \le d_n$; then $G$ is Hamiltonian if $G$ is $t$-tough and, $\forall i <\frac{n}{2},\mbox{ if } d_i\leq i \mbox{ then } d_{n-i+t}\geq n-i$. This conjecture is analogous to the well known theorem of Chvátal on Hamiltonian ideals. Hoàng proved the conjecture for $t\le 3$. Using the closure lemma for tough graphs, we prove the conjecture for $t=4$.