In this note, we present sufficient conditions involving the independence number, the minimum degree, and the maximum degree for some Hamiltonian properties of a graph.
We consider only finite undirected graphs without loops or multiple edges. Notation and terminology not defined here follow those in [1]. Let \(G = (V(G), E(G))\) be a graph with \(n\) vertices and \(e\) edges. We use \(\delta\) and \(\Delta\) to denote the minimum and maximum degrees of a graph \(G\), respectively. If \(T\) is a subset of \(V(G)\), we use \(G[T]\) to denote the subgraph of \(G\) induced by \(T\). A subset \(S\) of \(V(G)\) in \(G\) is independent if there is no edge between any pair of distinct vertices in \(S\). A maximum independent set in a graph \(G\) is an independent set of maximum cardinality. The independence number of a graph \(G\), denoted \(\alpha(G)\), is the size of a maximum independent set in \(G\). The join of two disjoint graphs \(H_1\) and \(H_2\) is denoted by \(H_1 \vee H_2\). For disjoint vertex subsets \(X\) and \(Y\) of \(V(G)\), we define \(E(X, Y)\) as \(\{\, e : e = xy \in E, x \in X, y \in Y \,\}\). A cycle \(C\) in a graph \(G\) is called a Hamilton cycle of \(G\) if \(C\) contains all the vertices of \(G\). We use \(K_{r, \, s}\) to denote a complete bipartite graph in which the two partition sets have cardinalities of \(r\) and \(s\), respectively. A graph \(G\) is called Hamiltonian if \(G\) has a Hamilton cycle. It is well-known that if \(G\) is Hamiltonian then \(|S| \geq \omega(G[V(G) – S])\) where \(S\) is any cutset of \(G\) and \(\omega(G[V(G) – S])\) is the number of components of the graph \(G[V(G) – S]\). A path \(P\) in a graph \(G\) is called a Hamilton path of \(G\) if \(P\) contains all the vertices of \(G\). A graph \(G\) is called traceable if \(G\) has a Hamilton path. It is well-known that if \(G\) is traceable then \(|S| + 1 \geq \omega(G[V(G) – S])\) where \(S\) is a cutset of \(G\) and \(\omega(G[V(G) – S])\) is the number of components of the graph \(G[V(G) – S]\). In this note, we present sufficient conditions involving the independence number, the minimum degree, and maximum degree for Hamiltonian graphs and traceable graphs.
Theorem 1.1. Let \(G\) be a \(k\)-connected (\(k \geq 2\)) graph with \(n \geq 3\) vertices, \(e\) edges, minimum degree \(\delta\), maximum degree \(\Delta\), and independence number \(\alpha\). Suppose \(G\) satisfies \[e \geq \frac{\alpha (n – k – 1 + \delta)^2}{8 \delta} + \frac{(n – k – 1)\Delta}{2}.\]
Then \(G\) is not Hamiltonian if and only if \(G \in\) \(\mathcal{H}\)\(_{1}\), where \(\mathcal{H}\)\(_{1} =\) \(\{ K^{c}_{k + 1} \vee Q: k \geq 2\) is a positive integer and \(Q\) is a regular graph of order \(k\)}.
Theorem 1.2. Let \(G\) be a \(k\)-connected (\(k \geq 1\)) graph with \(n \geq 3\) vertices, \(e\) edges, minimum degree \(\delta\), maximum degree \(\Delta\), and independence number \(\alpha\). Suppose \(G\) satisfies \[e \geq \frac{\alpha (n – k – 2 + \delta)^2}{8 \delta} + \frac{(n – k – 2)\Delta}{2}.\]
Then \(G\) is not traceable or \(G \in\) \(\mathcal{H}\)\(_{2}\), where \(\mathcal{H}\)\(_{2} =\) \(\{ K^{c}_{k + 2} \vee Q: k \geq 1\) is a positive integer and \(Q\) is a regular graph of order \(k\)}.
We will use the following results as lemmas in our proofs of Theorem 1.2 and Theorem 1.2. Lemma 2.1 below is Corollary \(4\) on Page \(67\) in [3]. See also [4].
Lemma 2.1. [3]. Let the real numbers \(\gamma_k\) (\(k = 1, 2, \cdots, n\)) satisfy \(0 < m \leq \gamma_k \leq M\). Then \[\sum_{k = 1}^n \gamma_k \, \sum_{k = 1}^n \frac{1}{\gamma_k} \leq \frac{(m + M)^2}{4mM} n^2.\]
If \(M > m\), the equality sign holds in above inequality if and only if \(n\) is an even number; while, at the same time, for \(n/2\) values of \(k\) one has \(\gamma_k = m\) and for the remaining \(n/2\) values of \(k\) one has \(\gamma_k = M\). If \(M = m\), the equality always holds in the above inequality.
Lemma 2.2 and Lemma 2.3 below are from [2].
Lemma 2.2. [2]. Let \(G\) be a \(k\)-connected graph of order \(n \geq 3\). If \(\alpha \leq k\), then \(G\) is Hamiltonian.
Lemma 2.3. [2]. Let \(G\) be a \(k\)-connected graph of order n. If \(\alpha \leq k + 1\), then \(G\) is traceable.
Proof of Theorem 1.1. Let \(G\) be a \(k\)-connected (\(k \geq 2\)) graph with \(n \geq 3\) vertices and \(e\) edges satisfying the conditions in Theorem 1.1. Suppose \(G\) is not Hamiltonian. We have that \(n \geq 2 \delta + 1 \geq 2 k + 1\) otherwise \(\delta \geq k \geq n/2\) and \(G\) is Hamiltonian. In addition, Lemma 2.2 implies that \(\alpha \geq k + 1\). Let \(I\) be any maximum independent set in \(G\). Then \(|I| = \alpha < n\). Notice that \(\delta \leq d(u) \leq n – \alpha\) for each vertex \(u \in I\). Applying Lemma 2.1, we have that \[\left(\sum_{u \in I} d(u) \right) \frac{\alpha}{n – \alpha} \leq \sum_{u \in I} d(u) \sum_{u \in I} \frac{1}{d(u)} \leq \frac{(n – \alpha + \delta)^2 }{4 \delta (n – \alpha)} \alpha^2.\]
Thus \[\sum_{u \in I} d(u) \leq \frac{\alpha (n – \alpha + \delta)^2 }{4 \delta}.\]
Therefore \[\begin{aligned} \frac{\alpha (n – k – 1 + \delta)^2}{4 \delta} + {(n – k – 1)\Delta} \leq& 2 e\\ =& \sum_{u \in I} d(u) + \sum_{v \in V – I} d(v)\\ \leq& \frac{\alpha (n – \alpha + \delta)^2 }{4 \delta} + (n – \alpha) \Delta\\ \leq& \frac{\alpha (n – k – 1 + \delta)^2}{4 \delta} + {(n – k – 1)\Delta}. \end{aligned}\]
Hence \[\begin{aligned} \frac{\alpha (n – k – 1 + \delta)^2}{4 \delta} + {(n – k – 1)\Delta} =& 2 e\\ =& \sum_{u \in I} d(u) + \sum_{v \in V – I} d(v)\\ =& \frac{\alpha (n – \alpha + \delta)^2 }{4 \delta} + (n – \alpha) \Delta. \end{aligned}\]
So \(\alpha = k + 1\), \(d(u) = n – \alpha = n – k – 1 = \delta\) for each \(u \in I\), and \(d(v) = \Delta \geq k + 1\) for each \(v \in V – I\).
If \(n – k – 1 \geq k + 1\), then \(\delta = n – k – 1 \geq \frac{n – k – 1 + k + 1}{2} = \frac{n}{2}\) and \(G\) is Hamiltonian, a contradiction. If \(n – k – 1 \leq k\). Then \(n \leq 2k + 1\). Thus \(n = 2k + 1\) and \(G \in\) \(\mathcal{H}\)\(_{1}\).
If \(G \in\) \(\mathcal{H}\)\(_{1}\), then \(n = 2k + 1\), \(\delta = k\), \(\alpha = k + 1\), \(\Delta \geq k + 1\), and \[\frac{k(k + 1)}{2} + \frac{k \Delta}{2} = e \geq \frac{\alpha (n – k – 1 + \delta)^2}{8 \delta} + \frac{(n – k – 1)\Delta}{2}.\]
For the cut set of \(V(Q)\), we have \(\omega(G[V(G) – V(Q)]) = k + 1 > k = |V(Q)|\). Thus \(G\) is not Hamiltonian.
This completes the proof of Theorem 1.1. ◻
Remark 3.1. We note that the exceptional graphs in Theorem 1.1 have not appeared in the well-known sufficient conditions for Hamiltonian graphs. This shows that Theorem 1.1 is unlikely implied by the existing theorems for Hamiltonian graphs.
The proof of Theorem 1.2 below is similar to the one of Theorem 1.1. For the sake of completeness, we still present a full proof of Theorem 1.2 below.
Proof of Theorem 1.2. Let \(G\) be a \(k\)-connected (\(k \geq 1\)) graph with \(n\) vertices and \(e\) edges satisfying the conditions in Theorem 1.2. If \(n = 1\) or \(n = 2\), it is clear that \(G\) is traceable. From now on, we assume that \(n \geq 3\). Suppose \(G\) is not traceable. We have that \(n \geq 2 \delta + 2 \geq 2 k + 2\) otherwise \(\delta \geq k \geq (n – 1)/2\) and \(G\) is traceable. In addition, Lemma 2.3 implies that \(\alpha \geq k + 2\). Let \(I\) be any maximum independent set in \(G\). Then \(|I| = \alpha < n\). Notice that \(\delta \leq d(u) \leq n – \alpha\) for each vertex \(u \in I\). Applying Lemma 2.1, we have that \[\left(\sum_{u \in I} d(u) \right) \frac{\alpha}{n – \alpha} \leq \sum_{u \in I} d(u) \sum_{u \in I} \frac{1}{d(u)} \leq \frac{(n – \alpha + \delta)^2 }{4 \delta (n – \alpha)} \alpha^2.\]
Thus \[\sum_{u \in I} d(u) \leq \frac{\alpha (n – \alpha + \delta)^2 }{4 \delta}.\]
Therefore \[\begin{aligned} \frac{\alpha (n – k – 2 + \delta)^2}{4 \delta} + {(n – k – 2)\Delta} &\leq 2 e\\ &= \sum_{u \in I} d(u) + \sum_{v \in V – I} d(v)\\ &\leq \frac{\alpha (n – \alpha + \delta)^2 }{4 \delta} + (n – \alpha) \Delta\\ &\leq \frac{\alpha (n – k – 2 + \delta)^2}{4 \delta} + {(n – k – 2)\Delta}. \end{aligned}\]
Hence \[\begin{aligned} \frac{\alpha (n – k – 2 + \delta)^2}{4 \delta} + {(n – k – 2)\Delta} &= 2 e\\ &= \sum_{u \in I} d(u) + \sum_{v \in V – I} d(v)\\ &= \frac{\alpha (n – \alpha + \delta)^2 }{4 \delta} + (n – \alpha) \Delta. \end{aligned}\]
So \(\alpha = k + 2\), \(d(u) = n – \alpha = n – k – 2 = \delta\) for each \(u \in I\), and \(d(v) = \Delta \geq k + 2\) for each \(v \in V – I\).
If \(n – k – 2 \geq k + 1\), then \(\delta = n – k – 2 \geq \frac{n – k – 2 + k + 1}{2} = \frac{n – 1}{2}\) and \(G\) is traceable, a contradiction. If \(n – k – 2 \leq k\). Then \(n \leq 2k + 2\). Thus \(n = 2k + 2\) and \(G \in\) \(\mathcal{H}\)\(_{2}\).
If \(G \in\) \(\mathcal{H}\)\(_{2}\), then \(n = 2k + 2\), \(\delta = k\), \(\alpha = k + 2\), \(\Delta \geq k + 2\), and \[\frac{k(k + 2)}{2} + \frac{k \Delta}{2} = e \geq \frac{\alpha (n – k – 2 + \delta)^2}{8 \delta} + \frac{(n – k – 2)\Delta}{2}.\]
For the cut set of \(V(Q)\), we have \(\omega(G[V(G)- V(Q)]) = k + 2 > k + 1 = |V(Q)| + 1\). Thus \(G\) is not traceable.
This completes the proof of Theorem 1.2. ◻
Remark 2. We note that the exceptional graphs in Theorem 1.2 have not appeared in the well-known sufficient conditions for traceable graphs. This shows that Theorem 1.2 is unlikely implied by the existing theorems for traceable graphs.
The author would like to thank the referee for his/her insightful suggestions and comments which improve the initial version of the paper.