The general inverse degree and some Hamiltonian properties of graphs

Li, Rao

doi:10.61091/jcmcc124-06

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 124
Pages: 87-98

Research article

The general inverse degree and some Hamiltonian properties of graphs

^¹

¹Deptartment of Computer Science, Engineering and Mathematics, University of South Carolina Aiken, Aiken, SC 29801, USA

Received: 29/08/2024
Accepted: 12/01/2025
Published Online: 16/03/2025

Copyright Link
License

Abstract

Let $G = (V, E)$ be a graph with minimum degree at least one. The general inverse degree of $G$ is defined as $\sum_{v \in V} \frac{1}{d^{α} (v)}$ , where $α$ is a real number with $α > 0$ . In this paper, we present sufficient conditions involving the general inverse degree with $α \geq 1$ for some Hamiltonian properties of graphs and upper bounds for the general inverse degree with $α \geq 1$ .

Keywords: the general, inverse degree, Hamiltonian graph, traceable graph

1. Introduction

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 $δ$ and $Δ$ 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 $β (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 = x y \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_{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_{v \in V (G)} d_{G}^{μ} (v)$ , where $μ$ is a real number such that $μ \neq 0$ and $μ \neq 1$ . When $μ < 0$ , the general first Zagreb index of a graph $G$ with $δ \geq 1$ is also called the general inverse degree of $G$ . Formally, the general inverse degree, denoted $G I D_{α} (G)$ , of $G$ with $δ \geq 1$ is defined as $\sum_{v \in V} \frac{1}{d_{G}^{α} (v)}$ , where $α$ is a real number with $α > 0$ . Notice that $G I D_{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 $α \geq 1$ , we in this paper present sufficient conditions for the Hamiltonian and traceable graphs and upper bounds for the general inverse degree with $α \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 $β$ . Assume $α$ is a real number with $α \geq 1$ .

a. Let $A_{1} := \frac{e^{α}}{(n - k - 1)^{α - 1}}$ . If $G I D_{α} (G) \geq \frac{k + 1}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - k - 1))^{2}}{4 A_{1} δ^{α} Δ^{α}},$ then $G$ is Hamiltonian.

b. Let $A_{2} := (k + 1) δ^{α} + \frac{e^{α}}{(n - k - 1)^{α - 1}}$ . If $G I D_{α} (G) \geq \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 A_{2} δ^{α} Δ^{α}},$ 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 $β$ . Assume $α$ is a real number with $α \geq 1$ .

a. Let $B_{1} := \frac{e^{α}}{(n - k - 2)^{α - 1}}$ . If $G I D_{α} (G) \geq \frac{k + 2}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - k - 2))^{2}}{4 B_{1} δ^{α} Δ^{α}},$ then $G$ is traceable.

b. Let $B_{2} := (k + 2) δ^{α} + \frac{e^{α}}{(n - k - 2)^{α - 1}}$ . If $G I D_{α} (G) \geq \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 B_{2} δ^{α} Δ^{α}},$ then $G$ is traceable.

Therem 1.3. Let $G$ be a graph with $n$ vertices, $e$ edges, the independence number $β$ , and the minimum degree $δ \geq 1$ . Assume $α$ is a real number with $α \geq 1$ .

a. Let $C_{1} := \frac{e^{α}}{(n - β)^{α - 1}}$ . Then $G I D_{α} (G) \leq \frac{β}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 C_{1} δ^{α} Δ^{α}}$ 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$ , $δ < Δ$ , $| V - I | = n - β$ is even, $d (u) = δ$ for each vertex $u \in I$ , $| {x : x \in V - I, d (x) = δ} | = \frac{n - β}{2}$ , $| {x : x \in V - I, d (x) = Δ} | = \frac{n - β}{2}$ , and $α = 1$ .

b. Let $C_{2} := β δ^{α} + \frac{e^{α}}{(n - β)^{α - 1}}$ . Then $G I D_{α} (G) \leq \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 C_{2} δ^{α} Δ^{α}}$ with equality if and only if $G$ is a regular balanced bipartite graph.

2. Lemma

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 $β$ . If $β \leq k$ , then $G$ is Hamiltonian.

Lemma 2.2. [3]. Let $G$ be a $k$ -connected graph of order $n$ with the independence number $β$ . If $β \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_{i = 1}^{m} a_{i} b_{i} \leq {(\sum_{i = 1}^{m} a_{i}^{p})}^{\frac{1}{p}} {(\sum_{i = 1}^{m} b_{i}^{q})}^{\frac{1}{q}} .$ Equality holds if and only if $\frac{a_{1}^{p}}{b_{1}^{q}} = \frac{a_{2}^{p}}{b_{2}^{q}} = \dots = \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 $γ_{k}$ ( $k = 1, 2, \dots, n$ ) satisfy $0 < m \leq γ_{k} \leq M$ . Then $\sum_{k = 1}^{n} γ_{k} \sum_{k = 1}^{n} \frac{1}{γ_{k}} \leq \frac{(m + M)^{2}}{4 m M} 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 $γ_{k} = m$ and for the remaining $n / 2$ values of $k$ one has $γ_{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 $2 n$ with bipartition ( $A$ , $B$ ). If $d (x) + d (y) \geq n + 1$ for any $x \in A$ and any $y \in B$ with $x y \notin 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, 2 s - 2)$ .

3. Proofs

Proof of Theorem 1.1. Let $G$ be a $k$ -connected ( $k \geq 2$ ) graph with $n \geq 3$ vertices and $e$ edges. Assume $α$ is a real number with $α \geq 1$ . Suppose $G$ is not Hamiltonian. Then Lemma $1$ implies that $β \geq k + 1$ . Also, we have that $n \geq 2 δ + 1 \geq 2 k + 1$ otherwise $δ \geq k \geq n / 2$ and $G$ is Hamiltonian. Let $I_{1} := {u_{1}, u_{2}, \dots, u_{β}}$ be a maximum independent set in $G$ . Then $I := {u_{1}, u_{2}, \dots, u_{k + 1}}$ is an independent set in $G$ . Let $V - I = {v_{1}, v_{2}, \dots, v_{n - (k + 1)}}$ . Clearly, $\sum_{u \in I} d (u) = | E_{G} (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) = 2 e$ , we have that $\sum_{u \in I} d (u) \leq e \leq \sum_{v \in V - I} d (v) .$

Applying Lemma $3$ with $m = n - (k + 1)$ , $a_{i} = d (v_{i})$ with $i = 1, 2, \dots, (n - (k + 1))$ , $b_{i} = 1$ with $i = 1, 2, \dots, (n - (k + 1))$ , $p = α > 1$ , and $q = \frac{p}{p - 1} = \frac{α}{α - 1}$ , we have $(n - (k + 1))^{\frac{α - 1}{α}} {(\sum_{i = 1}^{n - (k + 1)} d^{α} (v_{i}))}^{\frac{1}{α}} \geq \sum_{i = 1}^{n - (k + 1)} d (v_{i}) .$

Namely, $\sum_{i = 1}^{n - (k + 1)} d^{α} (v_{i}) \geq \frac{{(\sum_{i = 1}^{n - (k + 1)} d (v_{i}))}^{α}}{(n - (k + 1))^{α - 1}} \geq A_{1} := \frac{e^{α}}{(n - (k + 1))^{α - 1}} .$

Notice that the above inequality is also true when $α = 1$ .

a. Now $α \geq 1$ . Obviously, $0 < δ^{α} \leq d^{α} (v_{s}) \leq Δ^{α}$ , where $s = 1, 2, \dots, (n - (k + 1))$ . Applying Lemma 2.4, we have that $A_{1} \sum_{s = 1}^{n - (k + 1)} \frac{1}{d^{α} (v_{s})} \leq \sum_{s = 1}^{n - (k + 1)} d^{α} (v_{s}) \sum_{s = 1}^{n - (k + 1)} \frac{1}{d^{α} (v_{s})} \leq \frac{((δ^{α} + Δ^{α}) (n - k - 1))^{2}}{4 δ^{α} Δ^{α}} .$

Thus $\sum_{s = 1}^{n - (k + 1)} \frac{1}{d^{α} (v_{s})} \leq \frac{((δ^{α} + Δ^{α}) (n - k - 1))^{2}}{4 A_{1} δ^{α} Δ^{α}} .$

Therefore $\begin{aligned} \frac{k + 1}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - k - 1))^{2}}{4 A_{1} δ^{α} Δ^{α}} \leq & G I D_{α} (G) = \sum_{u \in I} \frac{1}{d^{α} (u)} + \sum_{v \in V - I} \frac{1}{d^{α} (v)}, \\ \leq & \frac{k + 1}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - k - 1))^{2}}{4 A_{1} δ^{α} Δ^{α}} . \end{aligned}$

Hence $d (u_{1}) = d (u_{2}) = \dots = d (u_{k + 1}) = δ$ , $\sum_{i = 1}^{n - (k + 1)} d (v_{i}) = e$ which implies $\sum_{i = 1}^{k + 1} d (u_{i}) = e$ and $G$ is a bipartite graph with partition sets of $I$ and $V - I$ , and $\sum_{s = 1}^{n - (k + 1)} d^{α} (v_{s}) \sum_{s = 1}^{n - (k + 1)} \frac{1}{d^{α} (v_{s})} = \frac{((δ^{α} + Δ^{α}) (n - k - 1))^{2}}{4 δ^{α} Δ^{α}} .$

Next, we will consider two cases.

Case 1. $δ = Δ$ .

In this case, we have $δ | I | = | E_{G} (I, V - I) | = δ | V - I |$ and thereby $| I | = | V - I | = k + 1$ . By Lemma 2.5, we have that $G$ is Hamiltonian, a contradiction.

Case 2. $δ < Δ$ .

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) = δ} | = \frac{n - (k + 1)}{2}$ , and $q := | {x : x \in V - I, d (x) = Δ} | = \frac{n - (k + 1)}{2}$ . Thus $δ | I | = | E_{G} (I, V - I) | = p δ + q Δ > (p + q) δ = (n - (k + 1)) δ$ . Hence $n < 2 k + 2$ . Recall that $n \geq 2 k + 1$ , we have that $n = 2 k + 1$ . Thus $G$ is $K_{k, k + 1}$ .

If $G$ is $K_{k, k + 1}$ , then $δ = k$ and $Δ = k + 1$ . Notice that $A_{1} = \frac{e^{α}}{(n - k - 1)^{α - 1}} = \frac{(δ Δ)^{α}}{δ^{α - 1}} = δ Δ^{α} .$

Since $\begin{aligned} \frac{Δ}{δ^{α}} + \frac{δ}{Δ^{α}} = & G I D_{α} (G), \\ = & \frac{k + 1}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - k - 1))^{2}}{4 A_{1} δ^{α} Δ^{α}}, \\ = & \frac{Δ}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) δ)^{2}}{4 δ Δ^{α} δ^{α} Δ^{α}}, \end{aligned}$ we have $(Δ^{α} - δ^{α})^{2} = 0$ . Thus $δ = Δ$ , a contradiction.

This completes the proofs of a in Theorem 1.1.

b. Now $α \geq 1$ . Recall that $\sum_{i = 1}^{n - (k + 1)} d^{α} (v_{i}) \geq \frac{{(\sum_{i = 1}^{n - (k + 1)} d (v_{i}))}^{α}}{(n - (k + 1))^{α - 1}} \geq \frac{e^{α}}{(n - (k + 1))^{α - 1}} .$

Thus $\sum_{x \in V} d^{α} (x) = \sum_{u \in I} d^{α} (u) + \sum_{v \in V - I} d^{α} (v) \geq A_{2} := (k + 1) δ^{α} + \frac{e^{α}}{(n - (k + 1))^{α - 1}} .$

We, from Lemma 2.4, have that $\frac{(n (δ^{α} + Δ^{α}))^{2}}{4 δ^{α} Δ^{α}} \leq A_{2} \sum_{x \in V} \frac{1}{d^{α} (x)} \leq \sum_{x \in V} d^{α} (x) \sum_{x \in V} \frac{1}{d^{α} (x)} \leq \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 δ^{α} Δ^{α}} .$

Hence $d (u_{1}) = d (u_{2}) = \dots = d (u_{k + 1}) = δ$ , $\sum_{i = 1}^{n - (k + 1)} d (v_{i}) = e$ which implies $\sum_{i = 1}^{k + 1} d (u_{i}) = e$ and $G$ is a bipartite graph with partition sets of $I$ and $V - I$ , and $\sum_{x \in V} d^{α} (x) \sum_{x \in V} \frac{1}{d^{α} (x)} = \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 δ^{α} Δ^{α}} .$

Next, we will consider two cases.

Case 1. $δ = Δ$ .

In this case, we have $δ | I | = | E_{G} (I, V - I) | = δ | V - I |$ and thereby $| I | = | V - I | = k + 1$ . By Lemma 2.5, we have that $G$ is Hamiltonian, a contradiction.

Case 2. $δ < Δ$ .

In this case, we, from Lemma 2.4, have that $n$ is even, either $d (v) = δ$ or $d (v) = Δ$ where $v$ is any vertex in $G$ , the size of $P := {x : x \in V, d (x) = δ}$ is $\frac{n}{2}$ , and the size of $Q := {x : x \in V, d (x) = Δ}$ is $\frac{n}{2}$ . Clearly, $I \subseteq P$ . If $I = P$ , then $n = 2 k + 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) = δ}$ and $Q_{1} := {x : x \in V - I, d (x) = Δ}$ . Obviously, $V - I = P_{1} \cup Q_{1}$ and $P_{1} \cap Q_{1} = \emptyset$ . Thus $δ | I | = | E_{G} (I, V - I) | = | P_{1} | δ + | Q_{1} | Δ > (| P_{1} | + | Q_{1} |) δ = (n - (k + 1)) δ$ . Hence $n < 2 k + 2$ . Recall that $n \geq 2 k + 1$ , we have that $n = 2 k + 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 $α$ is a real number with $α \geq 1$ . Suppose $G$ is not traceable. Then Lemma $2$ implies that $β \geq k + 2$ . Also, we have that $n \geq 2 δ + 2 \geq 2 k + 2$ otherwise $δ \geq k \geq (n - 1) / 2$ and $G$ is traceable. Let $I_{1} := {u_{1}, u_{2}, \dots, u_{β}}$ be a maximum independent set in $G$ . Then $I := {u_{1}, u_{2}, \dots, u_{k + 2}}$ is an independent set in $G$ . Let $V - I = {v_{1}, v_{2}, \dots, v_{n - (k + 2)}}$ . Clearly, $\sum_{u \in I} d (u) = | E_{G} (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) = 2 e$ , we have that $\sum_{u \in I} d (u) \leq e \leq \sum_{v \in V - I} d (v) .$

Applying Lemma $3$ with $m = n - (k + 2)$ , $a_{i} = d (v_{i})$ with $i = 1, 2, \dots, (n - (k + 2))$ , $b_{i} = 1$ with $i = 1, 2, \dots, (n - (k + 2))$ , $p = α > 1$ , and $q = \frac{p}{p - 1} = \frac{α}{α - 1}$ , we have $(n - (k + 2))^{\frac{α - 1}{α}} {(\sum_{i = 1}^{n - (k + 2)} d^{α} (v_{i}))}^{\frac{1}{α}} \geq \sum_{i = 1}^{n - (k + 2)} d (v_{i}) .$

Namely, $\sum_{i = 1}^{n - (k + 2)} d^{α} (v_{i}) \geq \frac{{(\sum_{i = 1}^{n - (k + 2)} d (v_{i}))}^{α}}{(n - (k + 2))^{α - 1}} \geq B_{1} := \frac{e^{α}}{(n - (k + 2))^{α - 1}} .$

Notice that the above inequality is also true when $α = 1$ .

a. Now $α \geq 1$ . Obviously, $0 < δ^{α} \leq d^{α} (v_{s}) \leq Δ^{α}$ , where $s = 1, 2, \dots, (n - (k + 2))$ . Applying Lemma 2.4, we have that $B_{1} \sum_{s = 1}^{n - (k + 2)} \frac{1}{d^{α} (v_{s})} \leq \sum_{s = 1}^{n - (k + 2)} d^{α} (v_{s}) \sum_{s = 1}^{n - (k + 2)} \frac{1}{d^{α} (v_{s})} \leq \frac{((δ^{α} + Δ^{α}) (n - k - 2))^{2}}{4 δ^{α} Δ^{α}} .$

Thus $\sum_{s = 1}^{n - (k + 2)} \frac{1}{d^{α} (v_{s})} \leq \frac{((δ^{α} + Δ^{α}) (n - k - 2))^{2}}{4 B_{1} δ^{α} Δ^{α}} .$

Therefore $\begin{aligned} \frac{k + 2}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - k - 2))^{2}}{4 B_{1} δ^{α} Δ^{α}} \leq G I D_{α} (G) = \\ \sum_{u \in I} \frac{1}{d^{α} (u)} + \sum_{v \in V - I} \frac{1}{d^{α} (v)} \leq \frac{k + 2}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - k - 2))^{2}}{4 B_{1} δ^{α} Δ^{α}} . \end{aligned}$

Hence $d (u_{1}) = d (u_{2}) = \dots = d (u_{k + 2}) = δ$ , $\sum_{i = 1}^{n - (k + 2)} d (v_{i}) = e$ which implies $\sum_{i = 1}^{k + 2} d (u_{i}) = e$ and $G$ is a bipartite graph with partition sets of $I$ and $V - I$ , and $\sum_{s = 1}^{n - (k + 2)} d^{α} (v_{s}) \sum_{s = 1}^{n - (k + 2)} \frac{1}{d^{α} (v_{s})} = \frac{((δ^{α} + Δ^{α}) (n - k - 2))^{2}}{4 δ^{α} Δ^{α}} .$

Next, we will consider two cases.

Case 1. $δ = Δ$ .

In this case, we have $δ | I | = | E_{G} (I, V - I) | = δ | V - I |$ and thereby $| I | = | V - I | = k + 2$ . Since $n = 2 k + 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. $δ < Δ$ .

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) = δ} | = \frac{n - (k + 2)}{2}$ , and $q := | {x : x \in V - I, d (x) = Δ} | = \frac{n - (k + 2)}{2}$ . Thus $δ | I | = | E_{G} (I, V - I) | = p δ + q Δ > (p + q) δ = (n - (k + 2)) δ$ . Hence $n < 2 k + 4$ . Recall that $n \geq 2 k + 2$ , we have that $n = 2 k + 3$ or $n = 2 k + 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 $δ = k$ and $Δ = k + 2$ . Notice that $B_{1} = \frac{e^{α}}{(n - k - 2)^{α - 1}} = \frac{(δ Δ)^{α}}{δ^{α - 1}} = δ Δ^{α} .$

Since $\frac{Δ}{δ^{α}} + \frac{δ}{Δ^{α}} = G I D_{α} (G) = \frac{k + 2}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - k - 2))^{2}}{4 B_{1} δ^{α} Δ^{α}}$ $= \frac{Δ}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) δ)^{2}}{4 δ Δ^{α} δ^{α} Δ^{α}},$ we have $(Δ^{α} - δ^{α})^{2} = 0$ . Thus $δ = Δ$ , a contradiction.

This completes the proofs of a. in Theorem 1.2.

b. Now $α \geq 1$ . Recall that $\sum_{i = 1}^{n - (k + 2)} d^{α} (v_{i}) \geq \frac{{(\sum_{i = 1}^{n - (k + 2)} d (v_{i}))}^{α}}{(n - (k + 2))^{α - 1}} \geq \frac{e^{α}}{(n - (k + 2))^{α - 1}} .$

Thus $\sum_{x \in V} d^{α} (x) = \sum_{u \in I} d^{α} (u) + \sum_{v \in V - I} d^{α} (v) \geq B_{2} := (k + 2) δ^{α} + \frac{e^{α}}{(n - (k + 2))^{α - 1}} .$

We, from Lemma 2.4, have that $\frac{(n (δ^{α} + Δ^{α}))^{2}}{4 δ^{α} Δ^{α}} \leq B_{2} \sum_{x \in V} \frac{1}{d^{α} (x)} \leq \sum_{x \in V} d^{α} (x) \sum_{x \in V} \frac{1}{d^{α} (x)} \leq \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 δ^{α} Δ^{α}} .$

Hence $d (u_{1}) = d (u_{2}) = \dots = d (u_{k + 2}) = δ$ , $\sum_{i = 1}^{n - (k + 2)} d (v_{i}) = e$ which implies $\sum_{i = 1}^{k + 2} d (u_{i}) = e$ and $G$ is a bipartite graph with partition sets of $I$ and $V - I$ , and $\sum_{x \in V} d^{α} (x) \sum_{x \in V} \frac{1}{d^{α} (x)} = \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 δ^{α} Δ^{α}} .$

Next, we will consider two cases.

Case 1. $δ = Δ$ .

Case 2. $δ < Δ$ .

In this case, we, from Lemma 2.4, have that $n$ is even, either $d (v) = δ$ or $d (v) = Δ$ where $v$ is any vertex in $G$ , the size of $P := {x : x \in V, d (x) = δ}$ is $\frac{n}{2}$ , and the size of $Q := {x : x \in V, d (x) = Δ}$ is $\frac{n}{2}$ . Clearly, $I \subseteq P$ . If $I = P$ , then $n = 2 k + 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) = δ}$ and $Q_{1} := {x : x \in V - I, d (x) = Δ}$ . Obviously, $V - I = P_{1} \cup Q_{1}$ and $P_{1} \cap Q_{1} = \emptyset$ . Thus $δ | I | = | E_{G} (I, V - I) | = | P_{1} | δ + | Q_{1} | Δ > (| P_{1} | + | Q_{1} |) δ = (n - (k + 2)) δ$ . Hence $n < 2 k + 4$ . Recall that $n \geq 2 k + 2$ , we have that $n = 2 k + 3$ or $n = 2 k + 2$ . Since $n$ is even, it is not possible that $n = 2 k + 3$ . If $n = 2 k + 2$ , then $k \geq 4$ since $n \geq 9$ . Thus $G$ is $K_{k, k + 2}$ . Thus $P := {x : x \in V, d (x) = δ}$ 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}, \dots, u_{β}}$ be a maximum independent set in $G$ . Set $V - I = {v_{1}, v_{2}, \dots, v_{n - β}}$ . Since $δ \geq 1$ , $β < n$ . Clearly, $\sum_{u \in I} d (u) = | E_{G} (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) = 2 e$ , we have that $\sum_{u \in I} d (u) \leq e \leq \sum_{v \in V - I} d (v) .$

Applying Lemma $3$ with $m = n - β$ , $a_{i} = d (v_{i})$ with $i = 1, 2, \dots, (n - β)$ , $b_{i} = 1$ with $i = 1, 2, \dots, (n - β)$ , $p = α > 1$ , and $q = \frac{p}{p - 1} = \frac{α}{α - 1}$ , we have $(n - β)^{\frac{α - 1}{α}} {(\sum_{i = 1}^{n - β} d^{α} (v_{i}))}^{\frac{1}{α}} \geq \sum_{i = 1}^{n - β} d (v_{i}) .$

Namely, $\sum_{i = 1}^{n - β} d^{α} (v_{i}) \geq \frac{{(\sum_{i = 1}^{n - β} d (v_{i}))}^{α}}{(n - β)^{α - 1}} \geq C_{1} := \frac{e^{α}}{(n - β)^{α - 1}} .$

Notice that the above inequality is also true when $α = 1$ .

a. Now $α \geq 1$ . Obviously, $0 < δ^{α} \leq d^{α} (v_{s}) \leq Δ^{α}$ , where $s = 1, 2, \dots, (n - β)$ . Applying Lemma 2.4, we have that $C_{1} \sum_{s = 1}^{n - β} \frac{1}{d^{α} (v_{s})} \leq \sum_{s = 1}^{n - β} d^{α} (v_{s}) \sum_{s = 1}^{n - β} \frac{1}{d^{α} (v_{s})}$ $\leq \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 δ^{α} Δ^{α}} .$

Thus $\sum_{s = 1}^{n - β} \frac{1}{d^{α} (v_{s})} \leq \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 C_{1} δ^{α} Δ^{α}} .$

Therefore $G I D_{α} (G) = \sum_{u \in I} \frac{1}{d^{α} (u)} + \sum_{v \in V - I} \frac{1}{d^{α} (v)}$ $\leq \frac{β}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 C_{1} δ^{α} Δ^{α}} .$

If $G I D_{α} (G) = \sum_{u \in I} \frac{1}{d^{α} (u)} + \sum_{v \in V - I} \frac{1}{d^{α} (v)}$ $= \frac{β}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 C_{1} δ^{α} Δ^{α}},$ then we have that $d (u_{1}) = d (u_{2}) = \dots = d (u_{β}) = δ$ , $\sum_{i = 1}^{n - β} d (v_{i}) = e$ which implies $\sum_{i = 1}^{β} d (u_{i}) = e$ and $G$ is a bipartite graph with partition sets of $I$ and $V - I$ , and $\sum_{s = 1}^{n - β} d^{α} (v_{s}) \sum_{s = 1}^{n - β} \frac{1}{d^{α} (v_{s})} = \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 δ^{α} Δ^{α}} .$

Next, we will consider two cases.

Case 1. $δ = Δ$ .

In this case, we have $δ | I | = | E_{G} (I, V - I) | = δ | 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. $δ < Δ$ .

In this case, we, from Lemma 2.4, have that $| V - I | = n - β$ is even, $| {x : x \in V - I, d (x) = δ} | = \frac{n - β}{2}$ , and $| {x : x \in V - I, d (x) = Δ} | = \frac{n - β}{2}$ .

Subcase 2.1 $α > 1$ .

In this case, we have $\sum_{i = 1}^{n - β} d^{α} (v_{i}) = \frac{{(\sum_{i = 1}^{n - β} d (v_{i}))}^{α}}{(n - β)^{α - 1}} = C_{1} := \frac{e^{α}}{(n - β)^{α - 1}} .$

Thus Lemma $3$ implies that that $d (v_{1}) = d (v_{2}) = \dots = d (v_{n - β}) := Δ$ . Notice that $C_{1} = \frac{e^{α}}{(n - β)^{α - 1}} = \frac{((n - β) Δ)^{α}}{(n - β)^{α - 1}} = (n - β) Δ^{α} .$

Since $\frac{β}{δ^{α}} + \frac{n - β}{Δ^{α}} = G I D_{α} (G) = \frac{β}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 C_{1} δ^{α} Δ^{α}}$ $= \frac{β}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 (n - β) Δ^{α} δ^{α} Δ^{α}},$ we have $\frac{n - β}{Δ^{α}} = \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 (n - β) Δ^{α} δ^{α} Δ^{α}} .$

Therefore $(Δ^{α} - δ^{α})^{2} = 0$ which implies that $δ = Δ$ , a contradiction.

Subcase 2.2 $α = 1$ .

In this case, $G$ is a bipartite graph with partition sets of $I$ and $V - I$ , $| V - I | = n - β$ is even, $d (u) = δ$ for each vertex $u \in I$ , $| {x : x \in V - I, d (x) = δ} | = \frac{n - β}{2}$ , and $| {x : x \in V - I, d (x) = Δ} | = \frac{n - β}{2}$ .

Next, we will show that the upper bound can be achieved by the special graphs.

If $α \geq 1$ and $G$ is a regular balanced bipartite graph, then $G I D_{α} (G) = \frac{n}{δ^{α}}$ , $δ = Δ$ , and $β = n - β = \frac{n}{2}$ . Notice that $C_{1} := \frac{e^{α}}{(n - β)^{α - 1}} = \frac{((n - β) Δ)^{α}}{(n - β)^{α - 1}} = \frac{n δ^{α}}{2} .$

Thus $\frac{β}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 C_{1} δ^{α} Δ^{α}} = \frac{n}{2 δ^{α}} + \frac{n}{2 δ^{α}} = \frac{n}{δ^{α}} = G I D_{α} (G) .$

If $α = 1$ and $G$ is a bipartite graph with partition sets of $I$ and $V - I$ , $δ < Δ$ , $| V - I | = n - β$ is even, $d (u) = δ$ for each vertex $u \in I$ , $| {x : x \in V - I, d (x) = δ} | = \frac{n - β}{2}$ , and $| {x : x \in V - I, d (x) = Δ} | = \frac{n - β}{2}$ , we first notice that $C_{1} := \frac{e^{α}}{(n - β)^{α - 1}} = e = \frac{n - β}{2} (δ + Δ)$ . Then $G I D_{1} (G) = \frac{β}{δ} + \frac{n - β}{2} \frac{1}{δ} + \frac{n - β}{2} \frac{1}{Δ} = \frac{β}{δ} + \frac{(n - β) (δ + Δ)}{2 δ Δ} .$

We also have $\frac{β}{δ} + \frac{((δ + Δ) (n - β))^{2}}{4 C_{1} δ Δ} = \frac{β}{δ} + \frac{(n - β) (δ + Δ)}{2 δ Δ} .$ Thus $G I D_{α} (G) = \frac{β}{δ^{α}} + \frac{((δ^{α} + Δ^{α}) (n - β))^{2}}{4 C_{1} δ^{α} Δ^{α}},$ where $α = 1$ and $C_{1} := \frac{e^{α}}{(n - β)^{α - 1}}$ .

This completes the proofs of a. in Theorem 1.3.

b. Now $α \geq 1$ . Recall that $\sum_{i = 1}^{n - β} d^{α} (v_{i}) \geq \frac{{(\sum_{i = 1}^{n - β} d (v_{i}))}^{α}}{(n - β)^{α - 1}} \geq \frac{e^{α}}{(n - β)^{α - 1}} .$

Thus $\sum_{x \in V} d^{α} (x) = \sum_{u \in I} d^{α} (u) + \sum_{v \in V - I} d^{α} (v) \geq C_{2} := β δ^{α} + \frac{e^{α}}{(n - β)^{α - 1}} .$

We, from Lemma 2.4, have that

$C_{2} \sum_{x \in V} \frac{1}{d^{α} (x)} \leq \sum_{x \in V} d^{α} (x) \sum_{x \in V} \frac{1}{d^{α} (x)} \leq \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 δ^{α} Δ^{α}} .$

Thus $G I D_{α} (G) \leq \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 C_{2} δ^{α} Δ^{α}} .$

If $G I D_{α} (G) = \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 C_{2} δ^{α} Δ^{α}},$ then we have that $d (u_{1}) = d (u_{2}) = \dots = d (u_{β}) = δ$ , $\sum_{i = 1}^{n - β} d (v_{i}) = e$ which implies $\sum_{i = 1}^{β} d (u_{i}) = e$ and $G$ is a bipartite graph with partition sets of $I$ and $V - I$ , and $\sum_{x \in V} d^{α} (x) \sum_{x \in V} \frac{1}{d^{α} (x)} = \frac{(n (δ^{α} + Δ^{α}))^{2}}{4 δ^{α} Δ^{α}} .$

Next, we will consider two cases.

Case 1. $δ = Δ$ .

In this case, we have $δ | I | = | E_{G} (I, V - I) | = δ | V - I |$ and thereby $| I | = | V - I | = β$ . Thus $G$ is a regular balanced bipartite graphs with partition sets of $I$ and $V - I$ .

Case 2. $δ < Δ$ .

In this case, we, from Lemma 2.4, have that $n$ is even, either $d (v) = δ$ or $d (v) = Δ$ where $v$ is any vertex in $G$ , the size of $P := {x : x \in V, d (x) = δ}$ is $\frac{n}{2}$ , and the size of $Q := {x : x \in V, d (x) = Δ}$ is $\frac{n}{2}$ . Clearly, $I \subseteq P$ . If $I = P$ , then $n = 2 β$ , $| I | = β$ , and $| V - I | = β$ . Since $I = P$ , $V - I = Q$ . Thus $δ | I | = | E_{G} (I, V - I) | = Δ | V - I |$ and $δ = Δ$ , a contradiction. If $I$ is a proper subset of $P$ . Set $P_{1} := {x : x \in V - I, d (x) = δ}$ and $Q_{1} := {x : x \in V - I, d (x) = Δ}$ . Obviously, $V - I = P_{1} \cup Q_{1}$ and $P_{1} \cap Q_{1} = \emptyset$ . Thus $δ | I | = | E_{G} (I, V - I) | = | P_{1} | δ + | Q_{1} | Δ > (| P_{1} | + | Q_{1} |) δ = (n - β) δ$ . Hence $n < 2 β$ . Thus $| P | = | I | + | P_{1} | = β + | P_{1} | > \frac{n}{2}$ , a contradiction.

If $α \geq 1$ and $G$ is a regular balanced bipartite graph, then $G I D_{α} (G) = \frac{n}{δ^{α}}$ , $δ = Δ$ , and $β = n - β = \frac{n}{2}$ . Notice that $C_{2} := β δ^{α} + \frac{e^{α}}{(n - β)^{α - 1}} = β δ^{α} + \frac{((n - β) Δ)^{α}}{(n - β)^{α - 1}} = \frac{n δ^{α}}{2} + \frac{n δ^{α}}{2} = n δ^{α} .$

Thus $\frac{(n (δ^{α} + Δ^{α}))^{2}}{4 C_{2} δ^{α} Δ^{α}} = \frac{n}{δ^{α}} = G I D_{α} (G) .$

This completes the proofs of b in Theorem 1.3.

Acknowledgment

The author would like to thank the referees for their suggestions which improve the initial version of the paper.

References:

A. Ali, I. Gutman, E. Milovanovic, and I. Milovanovic. Sum of powers of the degrees of graphs: extremal results and bounds. MATCH Communications in Mathematical and in Computer Chemistry, 80(1):5–84, 2018.
J. A. Bondy, U. S. R. Murty, et al. Graph Theory with Applications, volume 290. Macmillan London, 1976.
V. Chvátal and P. Erdös. A note on hamiltonian circuits. Discrete Mathematics, 2(2):111–113, 1972. https://doi.org/10.1016/0012-365X(72)90079-9.
J. B. Diaz and F. T. Metcalf. Complementary inequalities i: inequalities complementary to cauchy’s inequality for sums of real numbers. Journal of Mathematical Analysis and Applications, 9(1):59–74, 1964.
I. Gutman and N. Trinajstić. Graph theory and molecular orbitals. total φ-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4):535–538, 1972. https://doi.org/10.1016/0009-2614(72)85099-1.
B. Jackson. Long cycles in bipartite graphs. Journal of Combinatorial Theory, Series B, 38(2):118–131, 1985. https://doi.org/10.1016/0095-8956(85)90077-2.
A. Jahanbani and S. Sheikholeslam. The topological indices and some hamiltonian properties of graphs. Applied Mathematics E-Notes, 23:260–264, 2023.
R. Li. The hyper-zagreb index and some hamiltonian properties of graphs. Discrete Mathematics Letters, 1:54–58, 2019.
R. Li. The first general zagreb index and some hamiltonian properties of graphs. MATI, 6:43–48, 2024. http://www.doi.org/10.5281/zenodo.10521224.
R. Li. The general first zagreb index conditions for hamiltonian and traceable graphs. Discrete Mathematics Letters, 14:31–35, 2024. https://doi.org/10.47443/dml.2024.119.
R. Li. The inverse degree conditions for hamiltonian and traceable graphs. Open Journal of Discrete Applied Mathematics, 7:7–10, 2024. https://doi.org/10.30538/psrp-eas12024.0098.
R. Li and M. M. Taylor. The first zagreb index and some hamiltonian properties of the line graph of a graph. Journal of Discrete Mathematical Sciences and Cryptography, 20(2):445–451, 2017. https://doi.org/10.1080/09720529.2015.1103009.
X. Li and J. Zheng. A unified approach to the extremal trees for different indices. MATCH Communications in Mathematical and in Computer Chemistry, 54(1):195–208, 2005.
Y. Lu and Q. Zhou. On hyper-zagreb index conditions for hamiltonicity of graphs. Czechoslovak Mathematical Journal, 72(3):653–662, 2022. https://doi.org/10.21136/CMJ.2022.0089-21.
J. Moon and L. Moser. On hamiltonian bipartite graphs. Israel Journal of Mathematics, 1:163–165, 1963. https://doi.org/10.1007/BF02759704.
P. Schweitzer. Egy egyenlőtlenség az aritmetikai középértékről (an inequality concerning the arithmetic mean). Mathematikai és Physikai Lapok, 23:257–261, 1914.

[1] A. Ali, I. Gutman, E. Milovanovic, and I. Milovanovic. Sum of powers of the degrees of graphs: extremal results and bounds. MATCH Communications in Mathematical and in Computer Chemistry, 80(1):5–84, 2018.

[2] J. A. Bondy, U. S. R. Murty, et al. Graph Theory with Applications, volume 290. Macmillan London, 1976.

[3] V. Chvátal and P. Erdös. A note on hamiltonian circuits. Discrete Mathematics, 2(2):111–113, 1972. https://doi.org/10.1016/0012-365X(72)90079-9.

[4] J. B. Diaz and F. T. Metcalf. Complementary inequalities i: inequalities complementary to cauchy’s inequality for sums of real numbers. Journal of Mathematical Analysis and Applications, 9(1):59–74, 1964.

[5] I. Gutman and N. Trinajstić. Graph theory and molecular orbitals. total φ-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4):535–538, 1972. https://doi.org/10.1016/0009-2614(72)85099-1.

[6] B. Jackson. Long cycles in bipartite graphs. Journal of Combinatorial Theory, Series B, 38(2):118–131, 1985. https://doi.org/10.1016/0095-8956(85)90077-2.

[7] A. Jahanbani and S. Sheikholeslam. The topological indices and some hamiltonian properties of graphs. Applied Mathematics E-Notes, 23:260–264, 2023.

[8] R. Li. The hyper-zagreb index and some hamiltonian properties of graphs. Discrete Mathematics Letters, 1:54–58, 2019.

[9] R. Li. The first general zagreb index and some hamiltonian properties of graphs. MATI, 6:43–48, 2024. http://www.doi.org/10.5281/zenodo.10521224.

[10] R. Li. The general first zagreb index conditions for hamiltonian and traceable graphs. Discrete Mathematics Letters, 14:31–35, 2024. https://doi.org/10.47443/dml.2024.119.

[11] R. Li. The inverse degree conditions for hamiltonian and traceable graphs. Open Journal of Discrete Applied Mathematics, 7:7–10, 2024. https://doi.org/10.30538/psrp-eas12024.0098.

[12] R. Li and M. M. Taylor. The first zagreb index and some hamiltonian properties of the line graph of a graph. Journal of Discrete Mathematical Sciences and Cryptography, 20(2):445–451, 2017. https://doi.org/10.1080/09720529.2015.1103009.

[13] X. Li and J. Zheng. A unified approach to the extremal trees for different indices. MATCH Communications in Mathematical and in Computer Chemistry, 54(1):195–208, 2005.

[14] Y. Lu and Q. Zhou. On hyper-zagreb index conditions for hamiltonicity of graphs. Czechoslovak Mathematical Journal, 72(3):653–662, 2022. https://doi.org/10.21136/CMJ.2022.0089-21.

[15] J. Moon and L. Moser. On hamiltonian bipartite graphs. Israel Journal of Mathematics, 1:163–165, 1963. https://doi.org/10.1007/BF02759704.

[16] P. Schweitzer. Egy egyenlőtlenség az aritmetikai középértékről (an inequality concerning the arithmetic mean). Mathematikai és Physikai Lapok, 23:257–261, 1914.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

The general inverse degree and some Hamiltonian properties of graphs

Abstract

1. Introduction

2. Lemma

3. Proofs

Acknowledgment

References:

Information

Guidelines

CP Initiatives

Follow CP