Let \( G = (V, E) \) be a graph with minimum degree at least one. The general inverse degree of \( G \) is defined as \(\sum\limits_{v \in V} \frac{1}{d^{\alpha}(v)}\), where \( \alpha \) is a real number with \( \alpha > 0 \). In this paper, we present sufficient conditions involving the general inverse degree with \( \alpha \geq 1 \) for some Hamiltonian properties of graphs and upper bounds for the general inverse degree with \( \alpha \geq 1 \).
We consider only finite undirected graphs without loops or multiple edges. Notation and terminology not defined here follow those in [2]. Let \(G = (V(G), E(G))\) be a graph with \(n\) vertices and \(e\) edges, the degree of a vertex \(v\) is denoted by \(d_G(v)\). We use \(\delta\) and \(\Delta\) to denote the minimum degree and maximum degree of \(G\), respectively. A set of vertices in a graph \(G\) is independent if the vertices in the set are pairwise nonadjacent. A maximum independent set in a graph \(G\) is an independent set of largest possible size. The independence number, denoted \(\beta(G)\), of a graph \(G\) is the cardinality of a maximum independent set in \(G\). For disjoint vertex subsets \(X\) and \(Y\) of \(V(G)\), we use \(E_G(X, Y)\) to denote the set of all the edges in \(E(G)\) such that one end vertex of each edge is in \(X\) and another end vertex of the edge is in \(Y\). Namely, \(E_G(X, Y) := \{\, f : f = xy \in E, x \in X, y \in Y \,\}\). 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 [5]. For a graph \(G\), its first Zagreb index is defined as \(\sum\limits_{v \in V(G)} d_G^{2}(v)\). The concept of the first Zagreb index of a graph was further extended by Li and Zheng in [13]. They introduced the concept of the general first Zagreb index of a graph. The general first Zagreb index of a graph \(G\) is defined as \(\sum\limits_{v \in V(G)} d_G^{\mu}(v)\), where \(\mu\) is a real number such that \(\mu \neq 0\) and \(\mu \neq 1\). When \(\mu < 0\), the general first Zagreb index of a graph \(G\) with \(\delta \geq 1\) is also called the general inverse degree of \(G\). Formally, the general inverse degree, denoted \(GID_{\alpha}(G)\), of \(G\) with \(\delta \geq 1\) is defined as \(\sum\limits_{v \in V} \frac{1}{d^{\alpha}_G(v)}\), where \(\alpha\) is a real number with \(\alpha > 0\). Notice that \(GID_{1}(G)\) is called the inverse degree of \(G\). The survey paper [1] and references therein are good resources for the results on the general first Zagreb index of a graph. In recent years, sufficient conditions based on the first Zagreb index or the variants of the first Zagreb index for the Hamiltonian properties of graphs have been obtained. Some of them can be found in [12], [8], [14], [7], [9], [11], and [10]. Using the general inverse degree with \(\alpha \geq 1\), we in this paper present sufficient conditions for the Hamiltonian and traceable graphs and upper bounds for the general inverse degree with \(\alpha \geq 1\). The main results are as follows.
Therem 1.1. Let \(G\) be a \(k\)-connected (\(k \geq 2\)) graph with \(n \geq 3\) vertices, \(e\) edges, and the independence number \(\beta\). Assume \(\alpha\) is a real number with \(\alpha \geq 1\).
a. Let \(A_1 := \frac{e^{\alpha}}{(n – k – 1)^{\alpha – 1}}\). If \[GID_\alpha(G) \geq \frac{k + 1}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 1))^2}{4 A_1 \delta^{\alpha} \Delta^{\alpha}},\] then \(G\) is Hamiltonian.
b. Let \(A_2 := (k + 1) \delta^{\alpha} + \frac{e^{\alpha}}{(n – k – 1)^{\alpha – 1}}\). If \[GID_\alpha(G) \geq \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 A_2 \delta^{\alpha} \Delta^{\alpha}},\] then \(G\) is Hamiltonian.
Therem 1.2. Let \(G\) be a \(k\)-connected (\(k \geq 1\)) with \(n \geq 9\) vertices, \(e\) edges, and the independence number \(\beta\). Assume \(\alpha\) is a real number with \(\alpha \geq 1\).
a. Let \(B_1 := \frac{e^{\alpha}}{(n – k – 2)^{\alpha – 1}}\). If \[GID_\alpha(G) \geq \frac{k + 2}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 2))^2}{4 B_1 \delta^{\alpha} \Delta^{\alpha}},\] then \(G\) is traceable.
b. Let \(B_2 := (k + 2) \delta^{\alpha} + \frac{e^{\alpha}}{(n – k – 2)^{\alpha – 1}}\). If \[GID_\alpha(G) \geq \frac{(n(\delta^{\alpha} + \Delta^{\alpha}))^2}{4 B_2 \delta^{\alpha} \Delta^{\alpha}},\] then \(G\) is traceable.
Therem 1.3. Let \(G\) be a graph with \(n\) vertices, \(e\) edges, the independence number \(\beta\), and the minimum degree \(\delta \geq 1\). Assume \(\alpha\) is a real number with \(\alpha \geq 1\).
a. Let \(C_1 := \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}}\). Then \[GID_\alpha(G) \leq \frac{\beta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 C_1 \delta^{\alpha} \Delta^{\alpha}}\] with equality if and only if \(G\) is a regular balanced bipartite graph or \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), \(\delta < \Delta\), \(|V – I| = n – \beta\) is even, \(d(u) = \delta\) for each vertex \(u \in I\), \(|\{\, x : x \in V – I, d(x) = \delta\,\}| = \frac{n – \beta}{2}\), \(|\{\, x : x \in V – I, d(x) = \Delta\,\}| = \frac{n – \beta}{2}\), and \(\alpha = 1\).
b. Let \(C_2 := \beta \delta^{\alpha} + \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}}\). Then \[GID_\alpha(G) \leq \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 C_2 \delta^{\alpha} \Delta^{\alpha}}\] with equality if and only if \(G\) is a regular balanced bipartite graph.
We will use the following results as our lemmas. The first two are from [3].
Lemma 2.1. [3]. Let \(G\) be a \(k\)-connected graph of order \(n \geq 3\) with the independence number \(\beta\). If \(\beta \leq k\), then \(G\) is Hamiltonian.
Lemma 2.2. [3]. Let \(G\) be a \(k\)-connected graph of order \(n\) with the independence number \(\beta\). If \(\beta \leq k + 1\), then \(G\) is traceable.
Lemma 2.3 is the well-known Hőlder’s inequality.
Lemma 2.3. Let \(a_1\), \(a_2\), …, \(a_m\); \(b_1\), \(b_2\), …, \(b_m\) be positive real numbers and \(p\), \(q > 1\) be such that \(\frac{1}{p} + \frac{1}{q} = 1\). Then \[\sum\limits_{i = 1}^{m} a_ib_i \leq \left(\sum\limits_{i = 1}^{m}a_i^p\right)^{\frac{1}{p}} \left(\sum\limits_{i = 1}^{m}b_i^q\right)^{\frac{1}{q}}.\] Equality holds if and only if \(\frac{a_1^p}{b_1^q} = \frac{a_2^p}{b_2^q} = \cdots =\frac{a_m^p}{b_m^q}\).
Lemma 2.4 is Corollary \(4\) on Page \(67\) in [4]. See also [16].
Lemma 2.4. [4]. Let the real numbers \(\gamma_k\) (\(k = 1, 2, \cdots, n\)) satisfy \(0 < m \leq \gamma_k \leq M\). Then \[\sum\limits_{k = 1}^n \gamma_k \, \sum\limits_{k = 1}^n \frac{1}{\gamma_k} \leq \frac{(m + M)^2}{4mM} n^2.\] If \(M > m\), then 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.5 below is from [15].
Lemma 2.5. [15]. 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 2.6 below is from [6].
Lemma 2.6. [6]. 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 of Theorem 1.1. Let \(G\) be a \(k\)-connected (\(k \geq 2\)) graph with \(n \geq 3\) vertices and \(e\) edges. Assume \(\alpha\) is a real number with \(\alpha \geq 1\). Suppose \(G\) is not Hamiltonian. Then Lemma \(1\) implies that \(\beta \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_1 := \{\, u_1, u_2, …, u_{\beta} \,\}\) be a maximum independent set in \(G\). Then \(I := \{\, u_1, u_2, …, u_{k + 1} \,\}\) is an independent set in \(G\). Let \(V – I = \{\, v_1, v_2, …, v_{n – (k + 1)}\,\}\). Clearly, \[\sum\limits_{u \in I} d(u) = |E_G(I, V – I)| \leq \sum\limits_{v \in V – I} d(v).\]
Since \(\sum\limits_{u \in I} d(u) + \sum\limits_{v \in V – I} d(v) = 2e\), we have that \[\sum\limits_{u \in I} d(u) \leq e \leq \sum\limits_{v \in V – I} d(v).\]
Applying Lemma \(3\) with \(m = n – (k + 1)\), \(a_i = d(v_i)\) with \(i = 1, 2, …, (n – (k + 1))\), \(b_i = 1\) with \(i = 1, 2, …, (n – (k + 1))\), \(p = \alpha > 1\), and \(q = \frac{p}{p – 1} = \frac{\alpha}{\alpha – 1}\), we have \[(n – (k + 1))^{\frac{\alpha – 1}{\alpha}} \left(\sum\limits_{i = 1}^{n – (k + 1)} d^{\alpha}(v_i)\right)^{\frac{1}{\alpha}} \geq \sum\limits_{i = 1}^{n – (k + 1)} d(v_i).\]
Namely, \[\sum\limits_{i = 1}^{n – (k + 1)} d^{\alpha}(v_i) \geq \frac{\left(\sum\limits_{i = 1}^{n – (k + 1)} d(v_i)\right)^{\alpha}}{(n – (k + 1))^{\alpha – 1}} \geq A_1 := \frac{e^{\alpha}}{(n – (k + 1))^{\alpha – 1}}.\]
Notice that the above inequality is also true when \(\alpha = 1\).
a. Now \(\alpha \geq 1\). Obviously, \(0 < \delta^{\alpha} \leq d^{\alpha}(v_s) \leq \Delta^{\alpha}\), where \(s = 1, 2, …, (n – (k + 1))\). Applying Lemma 2.4, we have that \[A_1 \sum\limits_{s = 1}^{n – (k + 1)} \frac{1}{d^{\alpha}(v_s)} \leq \sum\limits_{s = 1}^{n – (k + 1)} d^{\alpha}(v_s) \sum\limits_{s = 1}^{n – (k + 1)} \frac{1}{d^{\alpha}(v_s)} \leq \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 1))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Thus \[\sum\limits_{s = 1}^{n – (k + 1)} \frac{1}{d^{\alpha}(v_s)} \leq \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 1))^2}{4 A_1 \delta^{\alpha} \Delta^{\alpha}}.\]
Therefore \[\begin{aligned} \frac{k + 1}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 1))^2}{4 A_1 \delta^{\alpha} \Delta^{\alpha}} \leq & GID_{\alpha}(G) = \sum\limits_{u \in I} \frac{1}{d^{\alpha}(u)} + \sum\limits_{v \in V – I} \frac{1}{d^{\alpha}(v)},\\ \leq &\frac{k + 1}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 1))^2}{4 A_1 \delta^{\alpha} \Delta^{\alpha}}. \end{aligned}\]
Hence \(d(u_1) = d(u_2) = \cdots = d(u_{k + 1}) = \delta\), \(\sum\limits_{i = 1}^{n – (k + 1)} d(v_i) = e\) which implies \(\sum\limits_{i = 1}^{k + 1} d(u_i) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), and \[\sum\limits_{s = 1}^{n – (k + 1)} d^{\alpha}(v_s) \sum\limits_{s = 1}^{n – (k + 1)} \frac{1}{d^{\alpha}(v_s)} = \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 1))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Next, we will consider two cases.
Case 1. \(\delta = \Delta\).
In this case, we have \(\delta \, |I| = |E_G(I, V – I)| = \delta |V – I|\) and thereby \(|I| = |V – I| = k + 1\). By Lemma 2.5, we have that \(G\) is Hamiltonian, a contradiction.
Case 2. \(\delta < \Delta\).
In this case, we, from Lemma 2.4, have that \(|V – I| = n – (k + 1)\) is even, \(p := |\{\, x : x \in V – I, d(x) = \delta\,\}| = \frac{n – (k + 1)}{2}\), and \(q := |\{\, x : x \in V – I, d(x) = \Delta\,\}| = \frac{n – (k + 1)}{2}\). Thus \(\delta |I| = |E_G(I, V – I)| = p \delta + q \Delta > (p + q) \delta = (n – (k + 1)) \delta\). Hence \(n < 2 k + 2\). Recall that \(n \geq 2 k + 1\), we have that \(n = 2k + 1\). Thus \(G\) is \(K_{k, \, k + 1}\).
If \(G\) is \(K_{k, \, k + 1}\), then \(\delta = k\) and \(\Delta = k + 1\). Notice that \[A_1 = \frac{e^{\alpha}}{(n – k – 1)^{\alpha – 1}} = \frac{(\delta \Delta)^{\alpha}}{\delta^{\alpha – 1}} = \delta \Delta^{\alpha}.\]
Since \[\begin{aligned} \frac{\Delta}{\delta^{\alpha}} + \frac{\delta}{\Delta^{\alpha}} =& GID_{\alpha}(G), \\ =& \frac{k + 1}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 1))^2}{4 A_1 \delta^{\alpha} \Delta^{\alpha}},\\ =& \frac{\Delta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})\delta)^2}{4 \delta \Delta^{\alpha} \delta^{\alpha} \Delta^{\alpha}}, \end{aligned}\] we have \((\Delta^{\alpha} – \delta^{\alpha})^2 = 0\). Thus \(\delta = \Delta\), a contradiction.
This completes the proofs of a in Theorem 1.1.
b. Now \(\alpha \geq 1\). Recall that \[\sum\limits_{i = 1}^{n – (k + 1)} d^{\alpha}(v_i) \geq \frac{\left(\sum\limits_{i = 1}^{n – (k + 1)} d(v_i)\right)^{\alpha}}{(n – (k + 1))^{\alpha – 1}} \geq \frac{e^{\alpha}}{(n – (k + 1))^{\alpha – 1}}.\]
Thus \[\sum\limits_{x \in V} d^{\alpha}(x) = \sum\limits_{u \in I} d^{\alpha}(u) + \sum\limits_{v \in V – I} d^{\alpha}(v) \geq A_2 := (k + 1) \delta^{\alpha} + \frac{e^{\alpha}}{(n – (k + 1))^{\alpha – 1}}.\]
We, from Lemma 2.4, have that \[\frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 \delta^{\alpha} \Delta^{\alpha}} \leq A_2 \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} \leq \sum\limits_{x \in V} d^{\alpha}(x) \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} \leq \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Hence \(d(u_1) = d(u_2) = \cdots = d(u_{k + 1}) = \delta\), \(\sum\limits_{i = 1}^{n – (k + 1)} d(v_i) = e\) which implies \(\sum\limits_{i = 1}^{k + 1} d(u_i) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), and \[\sum\limits_{x \in V} d^{\alpha}(x) \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} = \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Next, we will consider two cases.
Case 1. \(\delta = \Delta\).
In this case, we have \(\delta \, |I| = |E_G(I, V – I)| = \delta |V – I|\) and thereby \(|I| = |V – I| = k + 1\). By Lemma 2.5, we have that \(G\) is Hamiltonian, a contradiction.
Case 2. \(\delta < \Delta\).
In this case, we, from Lemma 2.4, have that \(n\) is even, either \(d(v) = \delta\) or \(d(v) = \Delta\) where \(v\) is any vertex in \(G\), the size of \(P := \{\, x : x \in V, \, d(x) = \delta\,\}\) is \(\frac{n}{2}\), and the size of \(Q := \{\, x : x \in V, \, d(x) = \Delta\,\}\) is \(\frac{n}{2}\). Clearly, \(I \subseteq P\). If \(I = P\), then \(n = 2k + 2\) and Lemma 2.5 implies \(G\) is Hamiltonian, a contradiction. If \(I\) is a proper subset of \(P\). Set \(P_1 := \{\, x : x \in V – I, \, d(x) = \delta\,\}\) and \(Q_1 := \{\, x : x \in V – I, \, d(x) = \Delta\,\}\). Obviously, \(V – I = P_1 \cup Q_1\) and \(P_1 \cap Q_1 = \emptyset\). Thus \(\delta |I| = |E_G(I, V – I)| = |P_1| \delta + |Q_1| \Delta > (|P_1| + |Q_1|) \delta = (n – (k + 1)) \delta\). Hence \(n < 2 k + 2\). Recall that \(n \geq 2 k + 1\), we have that \(n = 2k + 1\) and thereby \(n\) is odd, a contradiction.
This completes the proofs of b. in Theorem 1.1. ◻
The proofs of Theorem 1.2 are similar to ones of Theorem 1.1. For the sake of completeness, we still present the proofs of Theorem 1.2 below.
Proof of Theorem 1.2. Let \(G\) be a \(k\)-connected (\(k \geq 1\)) graph with \(n \geq 9\) vertices and \(e\) edges. Assume \(\alpha\) is a real number with \(\alpha \geq 1\). Suppose \(G\) is not traceable. Then Lemma \(2\) implies that \(\beta \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_1 := \{\, u_1, u_2, …, u_{\beta} \,\}\) be a maximum independent set in \(G\). Then \(I := \{\, u_1, u_2, …, u_{k + 2} \,\}\) is an independent set in \(G\). Let \(V – I = \{\, v_1, v_2, …, v_{n – (k + 2)}\,\}\). Clearly, \[\sum\limits_{u \in I} d(u) = |E_G(I, V – I)| \leq \sum\limits_{v \in V – I} d(v).\]
Since \(\sum\limits_{u \in I} d(u) + \sum\limits_{v \in V – I} d(v) = 2e\), we have that \[\sum\limits_{u \in I} d(u) \leq e \leq \sum\limits_{v \in V – I} d(v).\]
Applying Lemma \(3\) with \(m = n – (k + 2)\), \(a_i = d(v_i)\) with \(i = 1, 2, …, (n – (k + 2))\), \(b_i = 1\) with \(i = 1, 2, …, (n – (k + 2))\), \(p = \alpha > 1\), and \(q = \frac{p}{p – 1} = \frac{\alpha}{\alpha – 1}\), we have \[(n – (k + 2))^{\frac{\alpha – 1}{\alpha}} \left(\sum\limits_{i = 1}^{n – (k + 2)} d^{\alpha}(v_i)\right)^{\frac{1}{\alpha}} \geq \sum\limits_{i = 1}^{n – (k + 2)} d(v_i).\]
Namely, \[\sum\limits_{i = 1}^{n – (k + 2)} d^{\alpha}(v_i) \geq \frac{\left(\sum\limits_{i = 1}^{n – (k + 2)} d(v_i)\right)^{\alpha}}{(n – (k + 2))^{\alpha – 1}} \geq B_1 := \frac{e^{\alpha}}{(n – (k + 2))^{\alpha – 1}}.\]
Notice that the above inequality is also true when \(\alpha = 1\).
a. Now \(\alpha \geq 1\). Obviously, \(0 < \delta^{\alpha} \leq d^{\alpha}(v_s) \leq \Delta^{\alpha}\), where \(s = 1, 2, …, (n – (k + 2))\). Applying Lemma 2.4, we have that \[B_1 \sum\limits_{s = 1}^{n – (k + 2)} \frac{1}{d^{\alpha}(v_s)} \leq \sum\limits_{s = 1}^{n – (k + 2)} d^{\alpha}(v_s) \sum\limits_{s = 1}^{n – (k + 2)} \frac{1}{d^{\alpha}(v_s)} \leq \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 2))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Thus \[\sum\limits_{s = 1}^{n – (k + 2)} \frac{1}{d^{\alpha}(v_s)} \leq \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 2))^2}{4 B_1 \delta^{\alpha} \Delta^{\alpha}}.\]
Therefore \[\begin{aligned} &\frac{k + 2}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 2))^2}{4 B_1 \delta^{\alpha} \Delta^{\alpha}} \leq GID_{\alpha}(G) =\\& \sum\limits_{u \in I} \frac{1}{d^{\alpha}(u)} + \sum\limits_{v \in V – I} \frac{1}{d^{\alpha}(v)} \leq \frac{k + 2}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 2))^2}{4 B_1 \delta^{\alpha} \Delta^{\alpha}}. \end{aligned}\]
Hence \(d(u_1) = d(u_2) = \cdots = d(u_{k + 2}) = \delta\), \(\sum\limits_{i = 1}^{n – (k + 2)} d(v_i) = e\) which implies \(\sum\limits_{i = 1}^{k + 2} d(u_i) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), and \[\sum\limits_{s = 1}^{n – (k + 2)} d^{\alpha}(v_s) \sum\limits_{s = 1}^{n – (k + 2)} \frac{1}{d^{\alpha}(v_s)} = \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 2))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Next, we will consider two cases.
Case 1. \(\delta = \Delta\).
In this case, we have \(\delta \, |I| = |E_G(I, V – I)| = \delta |V – I|\) and thereby \(|I| = |V – I| = k + 2\). Since \(n = 2k + 4 \geq 9\), \(k \geq 3\). By Lemma 2.5, we have that \(G\) is Hamiltonian and thereby it is traceable, a contradiction.
Case 2. \(\delta < \Delta\).
In this case, we, from Lemma 2.4, have that \(|V
– I| = n – (k + 2)\) is even, \(p :=
|\{\, x : x \in V – I, d(x) = \delta\,\}| = \frac{n – (k +
2)}{2}\), and \(q := |\{\, x : x \in V
– I, d(x) = \Delta\,\}| = \frac{n – (k + 2)}{2}\). Thus \(\delta |I| = |E_G(I, V – I)| = p \delta + q \Delta
> (p + q) \delta = (n – (k + 2)) \delta\). Hence \(n < 2 k + 4\). Recall that \(n \geq 2 k + 2\), we have that \(n = 2k + 3\) or \(n = 2k + 2\). If \(n = 2 k + 3\), then \(k \geq 3\) since \(n \geq 9\). Thus Lemma \(6\) implies that \(G\) has a cycle of length at least \(2 k + 2 = n – 1\) and thereby \(G\) is traceable, a contradiction. If \(n = 2 k + 2\), then \(G\) is \(K_{k, \,
k + 2}\).
If \(G\) is \(K_{k, \, k + 2}\), then \(\delta = k\) and \(\Delta = k + 2\). Notice that \[B_1 = \frac{e^{\alpha}}{(n – k – 2)^{\alpha – 1}}
= \frac{(\delta \Delta)^{\alpha}}{\delta^{\alpha – 1}} = \delta
\Delta^{\alpha}.\]
Since \[\frac{\Delta}{\delta^{\alpha}} + \frac{\delta}{\Delta^{\alpha}} = GID_{\alpha}(G) = \frac{k + 2}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – k – 2))^2}{4 B_1 \delta^{\alpha} \Delta^{\alpha}}\] \[= \frac{\Delta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})\delta)^2}{4 \delta \Delta^{\alpha} \delta^{\alpha} \Delta^{\alpha}},\] we have \((\Delta^{\alpha} – \delta^{\alpha})^2 = 0\). Thus \(\delta = \Delta\), a contradiction.
This completes the proofs of a. in Theorem 1.2.
b. Now \(\alpha \geq 1\). Recall that \[\sum\limits_{i = 1}^{n – (k + 2)} d^{\alpha}(v_i) \geq \frac{\left(\sum\limits_{i = 1}^{n – (k + 2)} d(v_i)\right)^{\alpha}}{(n – (k + 2))^{\alpha – 1}} \geq \frac{e^{\alpha}}{(n – (k + 2))^{\alpha – 1}}.\]
Thus \[\sum\limits_{x \in V} d^{\alpha}(x) = \sum\limits_{u \in I} d^{\alpha}(u) + \sum\limits_{v \in V – I} d^{\alpha}(v) \geq B_2 := (k + 2) \delta^{\alpha} + \frac{e^{\alpha}}{(n – (k + 2))^{\alpha – 1}}.\]
We, from Lemma 2.4, have that \[\frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 \delta^{\alpha} \Delta^{\alpha}} \leq B_2 \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} \leq \sum\limits_{x \in V} d^{\alpha}(x) \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} \leq \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Hence \(d(u_1) = d(u_2) = \cdots = d(u_{k + 2}) = \delta\), \(\sum\limits_{i = 1}^{n – (k + 2)} d(v_i) = e\) which implies \(\sum\limits_{i = 1}^{k + 2} d(u_i) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), and \[\sum\limits_{x \in V} d^{\alpha}(x) \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} = \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Next, we will consider two cases.
Case 1. \(\delta = \Delta\).
In this case, we have \(\delta \, |I| = |E_G(I, V – I)| = \delta |V – I|\) and thereby \(|I| = |V – I| = k + 2\). Since \(n = 2k + 4 \geq 9\), \(k \geq 3\). By Lemma 2.5, we have that \(G\) is Hamiltonian and thereby it is traceable, a contradiction.
Case 2. \(\delta < \Delta\).
In this case, we, from Lemma 2.4, have that \(n\) is even, either \(d(v) = \delta\) or \(d(v) = \Delta\) where \(v\) is any vertex in \(G\), the size of \(P := \{\, x : x \in V, \, d(x) = \delta\,\}\) is \(\frac{n}{2}\), and the size of \(Q := \{\, x : x \in V, \, d(x) = \Delta\,\}\) is \(\frac{n}{2}\). Clearly, \(I \subseteq P\). If \(I = P\), then \(n = 2k + 4\). Since \(n \geq 9\), we have \(k \geq 3\). Thus Lemma 2.5 implies \(G\) is Hamiltonian and thereby it is traceable, a contradiction. If \(I\) is a proper subset of \(P\). Set \(P_1 := \{\, x : x \in V – I, \, d(x) = \delta\,\}\) and \(Q_1 := \{\, x : x \in V – I, \, d(x) = \Delta\,\}\). Obviously, \(V – I = P_1 \cup Q_1\) and \(P_1 \cap Q_1 = \emptyset\). Thus \(\delta |I| = |E_G(I, V – I)| = |P_1| \delta + |Q_1| \Delta > (|P_1| + |Q_1|) \delta = (n – (k + 2)) \delta\). Hence \(n < 2 k + 4\). Recall that \(n \geq 2 k + 2\), we have that \(n = 2k + 3\) or \(n = 2k + 2\). Since \(n\) is even, it is not possible that \(n = 2 k + 3\). If \(n = 2k + 2\), then \(k \geq 4\) since \(n \geq 9\). Thus \(G\) is \(K_{k, \, k + 2}\). Thus \(P := \{\, x : x \in V, \, d(x) = \delta\,\}\) is \(\frac{n + 2}{2}\), a contradiction.
This completes the proofs of b in Theorem 1.2. ◻
Proof of Theorem 1.3. Let \(I := \{\, u_1, u_2, …, u_{\beta} \,\}\) be a maximum independent set in \(G\). Set \(V – I = \{\, v_1, v_2, …, v_{n – \beta}\,\}\). Since \(\delta \geq 1\), \(\beta < n\). Clearly, \[\sum\limits_{u \in I} d(u) = |E_G(I, V – I)| \leq \sum\limits_{v \in V – I} d(v).\] Since \(\sum\limits_{u \in I} d(u) + \sum\limits_{v \in V – I} d(v) = 2e\), we have that \[\sum\limits_{u \in I} d(u) \leq e \leq \sum\limits_{v \in V – I} d(v).\]
Applying Lemma \(3\) with \(m = n – \beta\), \(a_i = d(v_i)\) with \(i = 1, 2, …, (n – \beta)\), \(b_i = 1\) with \(i = 1, 2, …, (n – \beta)\), \(p = \alpha > 1\), and \(q = \frac{p}{p – 1} = \frac{\alpha}{\alpha – 1}\), we have \[(n – \beta)^{\frac{\alpha – 1}{\alpha}} \left(\sum\limits_{i = 1}^{n – \beta} d^{\alpha}(v_i)\right)^{\frac{1}{\alpha}} \geq \sum\limits_{i = 1}^{n – \beta} d(v_i).\]
Namely, \[\sum\limits_{i = 1}^{n – \beta} d^{\alpha}(v_i) \geq \frac{\left(\sum\limits_{i = 1}^{n – \beta} d(v_i)\right)^{\alpha}}{(n – \beta)^{\alpha -1}} \geq C_1 := \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}}.\]
Notice that the above inequality is also true when \(\alpha = 1\).
a. Now \(\alpha \geq 1\). Obviously, \(0 < \delta^{\alpha} \leq d^{\alpha}(v_s) \leq \Delta^{\alpha}\), where \(s = 1, 2, …, (n – \beta)\). Applying Lemma 2.4, we have that \[C_1 \sum\limits_{s = 1}^{n – \beta} \frac{1}{d^{\alpha}(v_s)} \leq \sum\limits_{s = 1}^{n – \beta} d^{\alpha}(v_s) \sum\limits_{s = 1}^{n – \beta} \frac{1}{d^{\alpha}(v_s)}\] \[\leq \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Thus \[\sum\limits_{s = 1}^{n – \beta} \frac{1}{d^{\alpha}(v_s)} \leq \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 C_1 \delta^{\alpha} \Delta^{\alpha}}.\]
Therefore \[GID_{\alpha}(G) = \sum\limits_{u \in I} \frac{1}{d^{\alpha}(u)} + \sum\limits_{v \in V – I} \frac{1}{d^{\alpha}(v)}\] \[\leq \frac{\beta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 C_1 \delta^{\alpha} \Delta^{\alpha}}.\]
If \[GID_{\alpha}(G) = \sum\limits_{u \in I} \frac{1}{d^{\alpha}(u)} + \sum\limits_{v \in V – I} \frac{1}{d^{\alpha}(v)}\] \[= \frac{\beta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 C_1 \delta^{\alpha} \Delta^{\alpha}},\] then we have that \(d(u_1) = d(u_2) = \cdots = d(u_{\beta}) = \delta\), \(\sum\limits_{i = 1}^{n – \beta} d(v_i) = e\) which implies \(\sum\limits_{i = 1}^{\beta} d(u_i) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), and \[\sum\limits_{s = 1}^{n – \beta} d^{\alpha}(v_s) \sum\limits_{s = 1}^{n – \beta} \frac{1}{d^{\alpha}(v_s)} = \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Next, we will consider two cases.
Case 1. \(\delta = \Delta\).
In this case, we have \(\delta \, |I| = |E_G(I, V – I)| = \delta |V – I|\) and thereby \(|I| = |V – I| = k + 1\). Thus \(G\) is a regular balanced bipartite graph with partition sets of \(I\) and \(V – I\).
Case 2. \(\delta < \Delta\).
In this case, we, from Lemma 2.4, have that \(|V – I| = n – \beta\) is even, \(|\{\, x : x \in V – I, d(x) = \delta\,\}| = \frac{n – \beta}{2}\), and \(|\{\, x : x \in V – I, d(x) = \Delta\,\}| = \frac{n – \beta}{2}\).
Subcase 2.1 \(\alpha > 1\).
In this case, we have \[\sum\limits_{i = 1}^{n – \beta} d^{\alpha}(v_i) = \frac{\left(\sum\limits_{i = 1}^{n – \beta} d(v_i)\right)^{\alpha}}{(n – \beta)^{\alpha -1}} = C_1 := \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}}.\]
Thus Lemma \(3\) implies that that \(d(v_1) = d(v_2) = \cdots = d(v_{n – \beta}) : = \Delta\). Notice that \[C_1 = \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}} = \frac{((n – \beta) \Delta)^{\alpha}}{(n – \beta)^{\alpha – 1}} = (n – \beta) \Delta^{\alpha}.\]
Since \[\frac{\beta}{\delta^{\alpha}} + \frac{n – \beta}{\Delta^{\alpha}} = GID_{\alpha}(G)= \frac{\beta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 C_1 \delta^{\alpha} \Delta^{\alpha}}\] \[= \frac{\beta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 (n – \beta) \Delta^{\alpha} \delta^{\alpha} \Delta^{\alpha}},\] we have \[\frac{n – \beta}{\Delta^{\alpha}} = \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 (n – \beta) \Delta^{\alpha} \delta^{\alpha} \Delta^{\alpha}}.\]
Therefore \((\Delta^{\alpha} – \delta^{\alpha})^2 = 0\) which implies that \(\delta = \Delta\), a contradiction.
Subcase 2.2 \(\alpha = 1\).
In this case, \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), \(|V – I| = n – \beta\) is even, \(d(u) = \delta\) for each vertex \(u \in I\), \(|\{\, x : x \in V – I, d(x) = \delta\,\}| = \frac{n – \beta}{2}\), and \(|\{\, x : x \in V – I, d(x) = \Delta\,\}| = \frac{n – \beta}{2}\).
Next, we will show that the upper bound can be achieved by the special graphs.
If \(\alpha \geq 1\) and \(G\) is a regular balanced bipartite graph, then \(GID_\alpha(G) = \frac{n}{\delta^{\alpha}}\), \(\delta = \Delta\), and \(\beta = n – \beta = \frac{n}{2}\). Notice that \[C_1 := \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}} = \frac{((n – \beta) \Delta)^{\alpha}}{(n – \beta)^{\alpha – 1}} = \frac{n \delta^{\alpha}}{2}.\]
Thus \[\frac{\beta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 C_1 \delta^{\alpha} \Delta^{\alpha}} = \frac{n}{2 \delta^{\alpha}} + \frac{n}{2 \delta^{\alpha}} = \frac{n}{\delta^{\alpha}} = GID_\alpha(G).\]
If \(\alpha = 1\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), \(\delta < \Delta\), \(|V – I| = n – \beta\) is even, \(d(u) = \delta\) for each vertex \(u \in I\), \(|\{\, x : x \in V – I, d(x) = \delta\,\}| = \frac{n – \beta}{2}\), and \(|\{\, x : x \in V – I, d(x) = \Delta\,\}| = \frac{n – \beta}{2}\), we first notice that \(C_1 := \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}} = e = \frac{n – \beta}{2} (\delta + \Delta)\). Then \[GID_1(G) = \frac{\beta}{\delta} + \frac{n – \beta}{2} \frac{1}{\delta} + \frac{n – \beta}{2} \frac{1}{\Delta} = \frac{\beta}{\delta} + \frac{(n – \beta)(\delta + \Delta)}{2 \delta \Delta}.\]
We also have \[\frac{\beta}{\delta} + \frac{((\delta + \Delta)(n – \beta))^2}{4 C_1 \delta \Delta} = \frac{\beta}{\delta} + \frac{(n – \beta)(\delta + \Delta)}{2 \delta \Delta}.\] Thus \[GID_\alpha(G) = \frac{\beta}{\delta^{\alpha}} + \frac{((\delta^{\alpha} + \Delta^{\alpha})(n – \beta))^2}{4 C_1 \delta^{\alpha} \Delta^{\alpha}},\] where \(\alpha = 1\) and \(C_1 := \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}}\).
This completes the proofs of a. in Theorem 1.3.
b. Now \(\alpha \geq 1\). Recall that \[\sum\limits_{i = 1}^{n – \beta} d^{\alpha}(v_i) \geq \frac{\left(\sum\limits_{i = 1}^{n – \beta} d(v_i)\right)^{\alpha}}{(n – \beta)^{\alpha – 1}} \geq \frac{e^{\alpha}}{(n – \beta)^{\alpha -1}}.\]
Thus \[\sum\limits_{x \in V} d^{\alpha}(x) = \sum\limits_{u \in I} d^{\alpha}(u) + \sum\limits_{v \in V – I} d^{\alpha}(v) \geq C_2 := \beta \delta^{\alpha} + \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}}.\]
We, from Lemma 2.4, have that
\[C_2 \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} \leq \sum\limits_{x \in V} d^{\alpha}(x) \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} \leq \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Thus \[GID_\alpha(G) \leq \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 C_2 \delta^{\alpha} \Delta^{\alpha}}.\]
If \[GID_\alpha(G) = \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 C_2 \delta^{\alpha} \Delta^{\alpha}},\] then we have that \(d(u_1) = d(u_2) = \cdots = d(u_{\beta}) = \delta\), \(\sum\limits_{i = 1}^{n – \beta} d(v_i) = e\) which implies \(\sum\limits_{i = 1}^{\beta} d(u_i) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\), and \[\sum\limits_{x \in V} d^{\alpha}(x) \sum\limits_{x \in V} \frac{1}{d^{\alpha}(x)} = \frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 \delta^{\alpha} \Delta^{\alpha}}.\]
Next, we will consider two cases.
Case 1. \(\delta = \Delta\).
In this case, we have \(\delta \, |I| = |E_G(I, V – I)| = \delta |V – I|\) and thereby \(|I| = |V – I| = \beta\). Thus \(G\) is a regular balanced bipartite graphs with partition sets of \(I\) and \(V – I\).
Case 2. \(\delta < \Delta\).
In this case, we, from Lemma 2.4, have that \(n\) is even, either \(d(v) = \delta\) or \(d(v) = \Delta\) where \(v\) is any vertex in \(G\), the size of \(P := \{\, x : x \in V, \, d(x) = \delta\,\}\) is \(\frac{n}{2}\), and the size of \(Q := \{\, x : x \in V, \, d(x) = \Delta\,\}\) is \(\frac{n}{2}\). Clearly, \(I \subseteq P\). If \(I = P\), then \(n = 2 \beta\), \(|I| = \beta\), and \(|V – I| = \beta\). Since \(I = P\), \(V – I = Q\). Thus \(\delta |I| = |E_G(I, V – I)| = \Delta |V – I|\) and \(\delta = \Delta\), a contradiction. If \(I\) is a proper subset of \(P\). Set \(P_1 := \{\, x : x \in V – I, \, d(x) = \delta\,\}\) and \(Q_1 := \{\, x : x \in V – I, \, d(x) = \Delta\,\}\). Obviously, \(V – I = P_1 \cup Q_1\) and \(P_1 \cap Q_1 = \emptyset\). Thus \(\delta |I| = |E_G(I, V – I)| = |P_1| \delta + |Q_1| \Delta > (|P_1| + |Q_1|) \delta = (n – \beta) \delta\). Hence \(n < 2 \beta\). Thus \(|P| = |I| + |P_1| = \beta + |P_1| > \frac{n}{2}\), a contradiction.
If \(\alpha \geq 1\) and \(G\) is a regular balanced bipartite graph, then \(GID_\alpha(G) = \frac{n}{\delta^{\alpha}}\), \(\delta = \Delta\), and \(\beta = n – \beta = \frac{n}{2}\). Notice that \[C_2 := \beta \delta^{\alpha} + \frac{e^{\alpha}}{(n – \beta)^{\alpha – 1}} = \beta \delta^{\alpha} + \frac{((n – \beta) \Delta)^{\alpha}}{(n – \beta)^{\alpha – 1}} = \frac{n \delta^{\alpha}}{2} + \frac{n \delta^{\alpha}}{2} = n \delta^{\alpha}.\]
Thus \[\frac{(n (\delta^{\alpha} + \Delta^{\alpha}))^2}{4 C_2 \delta^{\alpha} \Delta^{\alpha}} = \frac{n}{\delta^{\alpha}} = GID_\alpha(G).\]
This completes the proofs of b in Theorem 1.3. ◻
The author would like to thank the referees for their suggestions which improve the initial version of the paper.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.