Let \(G = (V(G), E(G))\) be a graph with minimum degree at least \(1\). The inverse degree of \(G\), denoted \(Id(G)\), is defined as the sum of the reciprocals of degrees of all vertices in \(G\). In this note, we present inverse degree conditions for Hamiltonian and traceable graphs.
We consider only finite undirected graphs without loops or multiple edges. Notation and terminology not defined here follow those in [1]. For a graph \(G = (V(G), E(G))\), we use \(n\), \(e\), \(\delta(G)\), and \(\Delta(G)\) to denote order \(|V(G)|\), size \(|E(G)|\), minimum degree, and maximum degree of a graph \(G\), respectively. A subset \(V_1\) of the vertex set \(V(G)\) of \(G\) is independent if no two vertices in \(V_1\) are adjacent in \(G\). A maximum independent set in a graph \(G\) is an independent set of the largest possible size. The independence number of a graph \(G\), denoted \(\alpha(G)\), is the cardinality of a maximum independent set in \(G\). 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 \,\}\).
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 cycle \(C\) in a graph \(G\) is called a Hamiltonian cycle of \(G\) if \(C\) contains all the vertices of \(G\). A graph \(G\) is called Hamiltonian if \(G\) has a Hamiltonian cycle. A path \(P\) in a graph \(G\) is called a Hamiltonian path of \(G\) if \(P\) contains all the vertices of \(G\). A graph \(G\) is called traceable if \(G\) has a Hamiltonian path.
The first Zagreb index was introduced by Gutman and Trinajstić in [2]. For a graph \(G\), its first Zagreb index is defined as
\(\sum_{v \in V(G)} d_G^{2}(v)\). Li
and Zheng in [3] further
extended the first Zagreb index of a graph and introduced the concept of
the first general Zagreb index of a graph. The first general Zagreb
index of a graph \(G\) is defined as
\(\sum_{v \in V(G)} d_G^{r}(v)\), where
\(r\) is a real number such that \(r \neq 0\) and \(r \neq 1\). Let \(G\) be a graph with minimum degree at least
\(1\). The inverse degree of \(G\), denoted \(Id(G)\), is defined as the sum of the
reciprocals of degrees of all vertices in \(G\). Namely, \(Id(G) := \sum_{v \in
V(G)}\frac{1}{d_G(v)}\) and indeed it is the special first
general Zagreb index of \(G\) with
\(r = -1\). In recent years, sufficient
conditions based on the first Zagreb index or the first general index
for the Hamiltonian properties of graphs have been obtained. Some of
them can be found in [3-7]. In this note, we present inverse
degree conditions for Hamiltonian and traceable graphs. The main results
are as follows.
Theorem 1. Let \(G\) be a \(k\)-connected (\(k \geq 2\)) graph with \(n \geq 3\) vertices and \(e\) edges. If \[Id(G) \leq \frac{(k + 1)^2}{e} + \frac{n – (k + 1)}{\Delta},\] then \(G\) is Hamiltonian or \(K_{k, \, k + 1}\).
Theorem 2. Let \(G\) be a \(k\)-connected (\(k \geq 1\)) with \(n \geq 9\) vertices and \(e\) edges. If \[Id(G) \leq \frac{(k + 2)^2}{e} + \frac{n – (k + 2)}{\Delta},\] then \(G\) is traceable or \(K_{k, \, k + 2}\).
We will use the following results as our lemmas. The first two are from [8].
Lemma 3. [8]. Let \(G\) be a \(k\)-connected graph of order \(n \geq 3\). If \(\alpha \leq k\), then \(G\) is Hamiltonian.
Lemma 4. [8]. Let \(G\) be a \(k\)-connected graph of order n. If \(\alpha \leq k + 1\), then \(G\) is traceable.
Lemma 5. [9]. Let \(G\) be a balanced bipartite graph of order \(2n\) with bipartition (\(A\), \(B\)). If \(d(x) + d(y) \geq n + 1\) for any \(x \in A\) and any \(y \in B\) with \(xy \not \in E\), then \(G\) is Hamiltonian.
Lemma 6. [10]. Let \(G\) be a \(2\)-connected bipartite graph with bipartition (\(A\), \(B\)), where \(|A| \geq |B|\). If each vertex in \(A\) has degree at least \(s\) and each vertex in \(B\) has degree at least \(t\), then \(G\) contains a cycle of length at least \(2\min \{|B|, s + t – 1, 2s – 2\}\).
Proof. (Theorem 1.) Let \(G\) be a graph satisfying the conditions in Theorem 1. Suppose \(G\) is not Hamiltonian. Then Lemma 3 implies that \(\alpha \geq k + 1\). Also, we have that \(n \geq 2 \delta + 1 \geq 2 k + 1\) otherwise \(\delta \geq k \geq n/2\) and \(G\) is Hamiltonian. Let \(I := \{\, u_1, u_2, …, u_{k + 1} \,\}\) be an independent set in \(G\). Thus \[\sum_{u \in I} d(u) = |E(I, V – I)| \leq \sum_{v \in V – I} d(v).\] Since \(\sum_{u \in I} d(u) + \sum_{v \in V – I} d(v) = 2e\), we have that \[\sum_{u \in I} d(u) \leq e \leq \sum_{v \in V – I} d(v).\] Applying AM-GM-HM inequalities to \(d(u_1)\), \(d(u_2)\), …, \(d(u_{k + 1})\), we have that \[\sum_{u \in I}\frac{1}{d(u)} \geq \frac{|I|^2}{\sum_{u \in I} d(u)} \geq \frac{(k + 1)^2}{e}.\] From the conditions in Theorem \(1\), we have that \[\frac{(k + 1)^2}{e} + \frac{n – (k + 1)}{\Delta} \geq Id(G) = \sum_{u \in I}\frac{1}{d(u)} + \sum_{u \in V – I}\frac{1}{d(u)} \geq \frac{(k + 1)^2}{e} + \sum_{u \in V – I}\frac{1}{\Delta} = \frac{(k + 1)^2}{e} + \frac{n – (k + 1)}{\Delta}.\] Thus \[\frac{(k + 1)^2}{e} + \frac{n – (k + 1)}{\Delta} = Id(G) = \sum_{u \in I}\frac{1}{d(u)} + \sum_{u \in V – I}\frac{1}{d(u)} = \frac{(k + 1)^2}{e} + \sum_{u \in V – I}\frac{1}{\Delta} = \frac{(k + 1)^2}{e} + \frac{n – (k + 1)}{\Delta}.\] Therefore we have that \[\sum_{u \in I}\frac{1}{d(u)} = \frac{|I|^2}{\sum_{u \in I} d(u)},\;\;\; \sum_{u \in I} d(u) = e = |E(I, V – I)|,\] and the degree of each vertex in V – I is equal to \(\Delta\).
Hence \[d(u_1) = d(u_2) = \cdots = d(u_{k + 1}),\] \[\sum_{u \in I} d(u) = e = |E(I, V – I)| = \sum_{v \in V – I} d(v),\] and the degree of each vertex in V – I is equal to \(\Delta\).
Since \(\sum_{u \in I} d(u) = e = |E(I, V – I)| = \sum_{v \in V – I} d(v)\), \(V – I\) must be independent. Since \(|V| \geq 2k + 1\), we just need to consider the following possible cases.
If \(n = 2 k + 1\), then \(|V – I| = 2 k + 1 – |I| = 2 k + 1 – k – 1 = k\). Since \(d(u_1) = d(u_2) = \cdots = d(u_{k + 1}) \geq \delta \geq k\), we have that each vertex in \(I\) and each vertex in \((V – I)\) are adjacent. Thus \(G\) is \(K_{k, \, k + 1}\)
If \(n = 2 k + 2\), then \(\sum_{u \in I} d(u) = (k + 1) d(u_1) = e = (n – (k + 1)) \Delta = (k + 1) \Delta\). Thus \(d(u_1) = \Delta \geq k\). By Lemma 5, we have that \(G\) is Hamiltonian, a contradiction.
If \(n \geq 2 k + 3\), then \(\sum_{u \in I} d(u) = (k + 1) d(u_1) = e = (n – (k + 1)) \Delta \geq (k + 2) \Delta \geq (k + 2) d(u_1)\), a contradiction.
This completes the proofs of Theorem 1. ◻
The proof of Theorem 2 below is similar to the proof of Theorem 1 above. For the sake of the completeness, we still include the full proof of Theorem 2 here.
Proof. (Theorem 2.) Let \(G\) be a graph satisfying the conditions in Theorem 2. Suppose \(G\) is not traceable. Then Lemma 4 implies that \(\alpha \geq k + 2\). Also, we have that \(n \geq 2 \delta + 2 \geq 2 k + 2\) otherwise \(\delta \geq k \geq (n – 1)/2\) and \(G\) is traceable. Let \(I := \{\, u_1, u_2, …, u_{k + 2} \,\}\) be an independent set in \(G\). Thus \[\sum_{u \in I} d(u) = |E(I, V – I)| \leq \sum_{v \in V – I} d(v).\] Since \(\sum_{u \in I} d(u) + \sum_{v \in V – I} d(v) = 2e\), we have that \[\sum_{u \in I} d(u) \leq e \leq \sum_{v \in V – I} d(v).\] Applying AM-GM-HM inequalities to \(d(u_1)\), \(d(u_2)\), …, \(d(u_{k + 2})\), we have that \[\sum_{u \in I}\frac{1}{d(u)} \geq \frac{|I|^2}{\sum_{u \in I} d(u)} \geq \frac{(k + 2)^2}{e}.\] From the conditions in Theorem 2, we have that \[\frac{(k + 2)^2}{e} + \frac{n – (k + 2)}{\Delta} \geq Id(G) = \sum_{u \in I}\frac{1}{d(u)} + \sum_{u \in V – I}\frac{1}{d(u)} \geq \frac{(k + 2)^2}{e} + \sum_{u \in V – I}\frac{1}{\Delta} = \frac{(k + 2)^2}{e} + \frac{n – (k + 2)}{\Delta}.\] Thus \[\frac{(k + 2)^2}{e} + \frac{n – (k + 2)}{\Delta} = Id(G) = \sum_{u \in I}\frac{1}{d(u)} + \sum_{u \in V – I}\frac{1}{d(u)} = \frac{(k + 2)^2}{e} + \sum_{u \in V – I}\frac{1}{\Delta} = \frac{(k + 2)^2}{e} + \frac{n – (k + 2)}{\Delta}.\] Therefore we have that \[\sum_{u \in I}\frac{1}{d(u)} = \frac{|I|^2}{\sum_{u \in I} d(u)}, \;\;\; \sum_{u \in I} d(u) = e = |E(I, V – I)|,\] and the degree of each vertex in V – I is equal to \(\Delta\).
Hence \[d(u_1) = d(u_2) = \cdots = d(u_{k + 2}),\;\;\; \sum_{u \in I} d(u) = e = |E(I, V – I)| = \sum_{v \in V – I} d(v),\] and the degree of each vertex in V – I is equal to \(\Delta\).
Since \(\sum_{u \in I} d(u) = e = |E(I, V – I)| = \sum_{v \in V – I} d(v)\), \(V – I\) must be independent. Since \(|V| \geq 2k + 2\), we just need to consider the following possible cases.
If \(n = 2 k + 2\), then \(|V – I| = 2 k + 2 – |I| = 2 k + 2 – k – 2 = k\). Since \(d(u_1) = d(u_2) = \cdots = d(u_{k + 2}) \geq \delta \geq k\), we have that each vertex in \(I\) and each vertex in \((V – I)\) are adjacent. Thus \(G\) is \(K_{k, \, k + 2}\)
If \(n = 2 k + 3\), then then \(k \geq 3\) and \(|V – I| = k + 1\). By Lemma 6, we have that \(G\) has a cycle of length at least \(2k + 2\). Thus \(G\) is traceable, a contradiction.
If \(n = 2 k + 4\), then \(k \geq 3\) and \(|I| = |V – I| = k + 2\). Notice that \(d(v) \geq \delta \geq k\) for each vertex \(v \in G\). By Lemma 5, \(G\) is Hamiltonian and therefore traceable, a contradiction.
If \(n \geq 2 k + 5\), then \(\sum_{u \in I} d(u) = (k + 2) d(u_1) = e = (n – (k + 2)) \Delta \geq (k + 3) \Delta \geq (k + 3) d(u_1)\), a contradiction.
This completes the proofs of Theorem 2. ◻
Remark 1. From the proof of Theorem 1, we have the following result on the inverse degree of a graph.
Corollary 7. Let \(G\) be a graph of order \(n\), size \(e\), and minimum degree \(\delta \geq 1\). Then \[Id(G) \geq \frac{\alpha^2}{e} + \frac{n – \alpha}{\Delta}.\] Equality holds if and only if \(G\) is a graph satisfying the following conditions. For any maximum independent set \(I\) in \(G\), \(d(u) = \delta\) if \(u \in I\), \(V – I\) is independent and \(d(v) = \delta_1 \geq \delta\) if \(v \in V – I\), and \(e = \alpha \delta = (n – \alpha) \delta_1\).
