The first Zagreb index of a graph is one of the most important topological indices in chemical graph theory. It is also an important invariant of general graphs. The first Zagreb index of a graph is defined as the sum of the squares of the degrees of the vertices in the graph. The research on the Hamiltonian properties of a graph is an important topic in graph theory. Use the Diaz-Metcalf inequality, we in this paper present new sufficient conditions based on the first Zagreb index for the Hamiltonian and traceable graphs. In addition, using the ideas of obtaining the sufficient conditions, we also present an upper bound for the first Zagreb index of a graph. The graphs achieving the upper bound are also characterized.
We consider only finite undirected graphs without loops or multiple edges. We use [1] as a reference for the notation and terminology not defined here. Let \(G = (V(G), E(G))\) be a graph. An independent set in \(G\) is a set of vertices in \(G\) such that for every two vertices in the set there is no edge connecting them. The independence number of a graph \(G\), denoted \(\beta(G)\), is the cardinality of a largest independent set. Suppose \(X\) and \(Y\) are two disjoint subsets of \(V(G)\), we define \(E(X, Y) := \{\, e : e = xy \in E, x \in X, y \in Y \,\}\).
A graph \(G\) is Hamiltonian if \(G\) has a cycle containing all the vertices of \(G\). A graph \(G\) is traceable if \(G\) has a path containing all the vertices of \(G\). The Hamiltonian problem, determining when a graph is Hamiltonian, is a major unsolved problem in graph theory. While investigating the Hamiltonian problem, researchers often focus on finding the sufficient conditions for the Hamiltonian properties such as the Hamiltonicity or traceability of a graph. The readers are referred to see the survey papers [2– 4] and references therein on the research of Hamiltonian problem in graph theory.
In 1972, Gutman and Trinajstić introduced the concept of the first Zagreb index of a graph in [5], see also [6]. The first Zagreb index of a graph \(G\), denoted \(Z_1(G)\), is defined as \(\sum\limits_{u \in V(G)} d_G^{2}(u)\), where \(d_G(u)\) is the degree of the vertex \(u\) in \(G\). After its introduction, the first Zagreb index has been intensively investigated and it is one of the important topological indices in chemical graph theory. The first Zagreb index is also an important invariant of general graphs. Researchers have obtained a lot of results on the first Zagreb index of a graph. The readers are referred to see the survey papers [7– 9], and the references therein on the research of the first Zagreb index of a graph.
In recent years, researchers have utilized the first Zagreb index and its variants to obtain sufficient conditions for the Hamiltonian and traceable graphs. Some results on this research can be found in [10– 18]. In this paper, we still work along this direction. In particular, using the Diaz-Metcalf inequality in [19], we present the first Zagreb index conditions for the Hamiltonian and traceable graphs. In addition, using the ideas of obtaining the sufficient conditions, we also present an upper bound for the first Zagreb index of a graph and characterize the graphs achieving the upper bound. The main results of this paper are as follows.
Theorem 1. Suppose \(G\) is a graph with \(n \geq 3\) vertices and \(e\) edges. If \(G\) is \(k\)-connected with \(k \geq 2\) and \[Z_1(G) \geq (n – k – 1)\Delta^2 + e (\delta + n – k – 1) – \delta (k + 1) (n – k – 1),\] then \(G\) is Hamiltonian or \(G\) is \(K_{k, \, k + 1}\), where \(\delta\) and \(\Delta\) are respectively the minimum and maximum degrees of the graph \(G\).
Theorem 2. Suppose \(G\) is a with \(n \geq 9\) vertices and \(e\) edges. If \(G\) is \(k\)-connected with \(k \geq 1\) and \[Z_1(G) \geq (n – k – 2)\Delta^2 + e (\delta + n – k – 2) – \delta (k + 2) (n – k – 2),\] then \(G\) is traceable or \(G\) is \(K_{k, \, k + 2}\), where \(\delta\) and \(\Delta\) are respectively the minimum and maximum degrees of the graph \(G\).
Theorem 3. Suppose \(G\) is a graph with \(n\) vertices and \(e\) edges. If the minimum degree \(\delta\) of \(G\) is at least \(1\), then \[Z_1(G) \leq (n – \beta)\Delta^2 + e (\delta + n – \beta) – \delta \beta (n – \beta) ,\] with equality if and only if \(G\) is \(K_{\beta, \, n – \beta}\) or \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \beta\), \(\delta < n – \beta\), \(d(v) = \Delta\) for each vertex \(v\) in \(V – I\), and \(I = P \cup Q\), where \(P = \{\, x : x \in I, d(x) = n – \beta \,\}\), \(Q = \{\, y : y \in I, d(y) = \delta \,\}\), where \(\Delta\) is the maximum degree of \(G\).
The following existing results will be used as our lemmas.
Lemma 1. [20] Suppose \(G\) is a \(k\)-connected graph of order \(n \geq 3\) with independence number \(\beta\). If \(\beta \leq k\), then \(G\) is Hamiltonian.
Lemma 2. [20] Suppose \(G\) is a \(k\)-connected graph of order n with independence number \(\beta\). If \(\beta \leq k + 1\), then \(G\) is traceable.
Lemma 3 follows from Theorem 1 on Page \(61\) and Page \(62\) in [19].
Lemma 3. [19] Let the real numbers \(a_k\) and \(b_k\) (\(k = 1, 2, \cdots, s\)) satisfy \(0 \leq m_1 \leq a_k \leq M_1\) and \(0 \leq m_2 \leq b_k \leq M_2\). Then \[m_1 M_1 \sum\limits_{k = 1}^s b_k^2 + m_2 M_2 \sum\limits_{k = 1}^s a_k^2 \leq (M_1 M_2 + m_1 m_2) \sum\limits_{k = 1}^s a_kb_k.\]
If \(0 < m_1\) and \(0 < m_2\), then the equality holds if and only if for each \(k\) one has either \((a_k, b_k) = (m_1, M_2)\) or \((a_k, b_k) = (M_1, m_2)\).
Lemma 4. [21] Suppose \(G\) is a bipartite graph of order \(2n\) with partition sets \(X\) and \(Y\) such that \(|X| = |Y| = n\). If \(d(x) + d(y) \geq n + 1\) for each \(xy \not \in E\), where \(x \in X\) and \(y \in Y\), then \(G\) is Hamiltonian.
Lemma 5. [22] Let \(G\) be a \(2\)-connected bipartite graph with partition sets \(X\) and \(Y\) such that \(|X| \geq |Y|\). If \(d(x) \geq s\), where \(x\) is any vertex in \(X\), and \(d(y) \geq t\), where \(y\) is any vertex in \(Y\), then \(G\) has a cycle of length at least \(2 \min (|Y|, s + t – 1, 2s – 2)\).
Before we present the proof of Theorem 1, let us recall Theorem 1.
Suppose \(G\) is a graph with \(n \geq 3\) vertices and \(e\) edges. If \(G\) is \(k\)-connected with \(k \geq 2\) and \[Z_1(G) \geq (n – k – 1)\Delta^2 + e (\delta + n – k – 1) – \delta (k + 1) (n – k – 1),\] then \(G\) is Hamiltonian or \(G\) is \(K_{k, \, k + 1}\), where \(\delta\) and \(\Delta\) are respectively the minimum and maximum degrees of the graph \(G\).
Proof of Theorem 1. Let \(G\) be a graph with \(n \geq 3\) vertices and \(e\) edges. Suppose \(G\) satisfies the conditions in Theorem 1 and \(G\) is not Hamiltonian. Since \(G\) is not Hamiltonian, then from Lemma 1 we have that \(k + 1 \leq \beta\). Furthermore, we have that \(n \geq 2 \delta + 1\) otherwise \(G\) is Hamiltonian since \(\delta \geq n/2\). Since \(\delta \geq k\), we have \(n \geq 2 k + 1\). Let \(S := \{\, u_1, u_2, …, u_{\beta} \,\}\) be an independent set of maximum cardinality in \(G\). Since \(\beta \geq k + 1\), we have that \(I := \{\, u_1, u_2, …, u_{k + 1} \,\}\) is an independent set in \(G\). Clearly, \[\sum\limits_{v \in V – I} d(v) \geq |E(I, V – I)| \geq \sum\limits_{u \in I} d(u).\]
From \(2e = \sum\limits_{v \in V – I} d(v) + \sum\limits_{u \in I} d(u)\), we have that \[\sum\limits_{v \in V – I} d(v) \geq e \geq \sum\limits_{u \in I} d(u).\]
Obviously, \(0 < \delta \leq d(u) \leq n – k – 1\) for each \(u \in I\). Applying Lemma 3 with \(s = k + 1\), \(a_i = 1\) and \(b_i = d(u_i)\) with \(i = 1, 2, … , (k + 1)\), \(m_1 = 1 > 0\), \(M_1 = 1\), \(m_2 = \delta > 0\), and \(M_2 = n – k – 1\), we have \[\sum\limits_{i = 1}^{k + 1} d^2(u_i) + \delta (n – k – 1) \sum\limits_{i = 1}^{k + 1} 1^2 \leq (\delta + n – k – 1)\sum\limits_{i = 1}^{k + 1} d(u_i) \leq (\delta + n – k – 1) e.\]
Thus \[\sum\limits_{i = 1}^{k + 1} d^2(u_i) \leq e (\delta + n – k – 1) – \delta (n – k – 1)(k + 1).\]
From the conditions in Theorem 1, we have that \[\begin{aligned}(n – k – 1)\Delta^2 + e (\delta + n – k – 1) – \delta (k + 1) (n – k – 1)& \leq Z_1 = \sum\limits_{v \in V – I} d^2(v) + \sum\limits_{u \in I} d^2(u)\\ &\leq (n – k – 1)\Delta^2 + e (\delta + n – k – 1) – \delta (k + 1) (n – k – 1).\end{aligned}\]
Therefore \[\begin{aligned}(n – k – 1)\Delta^2 + e (\delta + n – k – 1) – \delta (k + 1) (n – k – 1)&= Z_1 = \sum\limits_{v \in V – I} d^2(v) + \sum\limits_{u \in I} d^2(u)\\ &= (n – k – 1)\Delta^2 + e (\delta + n – k – 1) – \delta (k + 1) (n – k – 1).\end{aligned}\]
Hence \(d(v) = \Delta\) for each \(v \in V – I\), \[\sum\limits_{i = 1}^{k + 1} d^2(u_i) + \delta (n – k – 1) \sum\limits_{i = 1}^{k + 1} 1^2 = (\delta + n – k – 1) \sum\limits_{i = 1}^{k + 1} d(u_i),\] and \(\sum\limits_{i = 1}^{k + 1}d(u_i) = e\). Thus \(\sum\limits_{v \in V – I}d(v) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\) and \(\Delta = d(v) \leq k + 1\), where \(v\) is any vertex in \(V – I\).
The remaining proofs are divided into two cases.
Case 1. \(\delta = n – k – 1\).
In this case, we have \(d(u) = \delta\) for each \(u\) in \(I\). Thus \(\delta (k + 1) = |E(I, V – I)| = \Delta (n – k – 1) \geq \delta (n – k – 1)\). Therefore \(n \leq 2 k + 2\). Since \(n \geq 2 k + 1\), we have \(n = 2 k + 2\) or \(n = 2 k + 1\). If \(n = 2 k + 2\), we, from Lemma 4, have that \(G\) is Hamiltonian, a contradiction. If \(n = 2 k + 1\), then \(G\) is \(K_{k, \, k + 1}\).
Case 2. \(\delta < n – k – 1\).
In this case, we, from Lemma 3, have that \(I = P \cup Q\), where \(P = \{\, x : x \in I, d(x) = n – k – 1 \,\}\) and \(Q = \{\, y : y \in I, d(y) = \delta \,\}\). If \(|P| > 0\), then there exists a vertex \(z\) in \(I\) such that \(d(z) = n – k – 1\). Thus \(n – k – 1 = d(z) \leq \Delta \leq k + 1\). Thus \(n \leq 2 k + 2\). Since \(n \geq 2 k + 1\), we have \(n = 2 k + 2\) or \(n = 2 k + 1\). If \(n = 2 k + 2\), we, from Lemma 4, have that \(G\) is Hamiltonian, a contradiction. If \(n = 2 k + 1\), then \(G\) is \(K_{k, \, k + 1}\). Thus \(n – k – 1 = k = \delta\), a contradiction again. If \(|P| = 0\), then all the vertices in \(I\) have a degree of \(\delta\). Therefore \(\delta (k + 1) = |E(I, V – I)| = \Delta (n – k – 1) \geq \delta (n – k – 1)\). Thus \(n \leq 2 k + 2\). Since \(n \geq 2 k + 1\), we have \(n = 2 k + 2\) or \(n = 2 k + 1\). If \(n = 2 k + 2\), we, from Lemma 4, have that \(G\) is Hamiltonian, a contradiction. If \(n = 2 k + 1\), then \(G\) is \(K_{k, \, k + 1}\). Thus \(n – k – 1 = k = \delta\), a contradiction.
This completes the proof of Theorem 1. ◻
The proof of Theorem 2 is similar to the proof of Theorem 1. For the sake of completeness, we still present a full proof of Theorem 2 here. Before we present the proof of Theorem 2, let us recall Theorem 2.
Suppose \(G\) is a with \(n \geq 9\) vertices and \(e\) edges. If \(G\) is \(k\)-connected with \(k \geq 1\) and \[Z_1(G) \geq (n – k – 2)\Delta^2 + e (\delta + n – k – 2) – \delta (k + 2) (n – k – 2),\] then \(G\) is traceable or \(G\) is \(K_{k, \, k + 2}\), where \(\delta\) and \(\Delta\) are respectively the minimum and maximum degrees of the graph \(G\).
Proof of Theorem 2. Let \(G\) be a graph with \(n \geq 9\) vertices and \(e\) edges. Suppose \(G\) satisfies the conditions in Theorem 2 and \(G\) is not traceable. Since \(G\) is not traceable, then from Lemma 2 we have that \(k + 2 \leq \beta\). Furthermore, we have that \(n \geq 2 \delta + 2\) otherwise \(G\) is traceable since \(\delta \geq (n – 1)/2\). Since \(\delta \geq k\), we have \(n \geq 2 k + 2\). Let \(T := \{\, u_1, u_2, …, u_{\beta} \,\}\) be an independent set of maximum cardinality in \(G\). Since \(\beta \geq k + 2\), we have that \(I := \{\, u_1, u_2, …, u_{k + 2} \,\}\) is an independent set in \(G\). Clearly, \[\sum\limits_{v \in V – I} d(v) \geq |E(I, V – I)| \geq \sum\limits_{u \in I} d(u).\]
Since \(2e = \sum\limits_{v \in V – I} d(v) + \sum\limits_{u \in I} d(u)\), we have that \[\sum\limits_{v \in V – I} d(v) \geq e \geq \sum\limits_{u \in I} d(u).\]
Obviously, \(0 < \delta \leq d(u) \leq n – k – 2\) for each \(u \in I\). Applying Lemma 3 with \(s = k + 2\), \(a_i = 1\) and \(b_i = d(u_i)\) with \(i = 1, 2, … , (k + 2)\), \(m_1 = 1 > 0\), \(M_1 = 1\), \(m_2 = \delta > 0\), and \(M_2 = n – k – 2\), we have \[\sum\limits_{i = 1}^{k + 2} d^2(u_i) + \delta (n – k – 2) \sum\limits_{i = 1}^{k + 2} 1^2 \leq (\delta + n – k – 2)\sum\limits_{i = 1}^{k + 2} d(u_i) \leq (\delta + n – k – 2) e.\]
Thus \[\sum\limits_{i = 1}^{k + 2} d^2(u_i) \leq e (\delta + n – k – 2) – \delta (n – k – 2)(k + 2).\]
From the conditions in Theorem 2, we have that \[\begin{aligned}(n – k – 2)\Delta^2 + e (\delta + n – k – 2) – \delta (k + 2)(n – k – 2) \leq Z_1 &= \sum\limits_{v \in V – I} d^2(v) + \sum\limits_{u \in I} d^2(u)\\ &\leq (n – k – 2)\Delta^2 + e (\delta + n – k – 2) – \delta (k + 2) (n – k – 2).\end{aligned}\]
Therefore \[\begin{aligned}(n – k – 2)\Delta^2 + e (\delta + n – k – 2) – \delta (k + 2)(n – k – 2) = Z_1 &= \sum\limits_{v \in V – I} d^2(v) + \sum\limits_{u \in I} d^2(u)\\ &= (n – k – 2)\Delta^2 + e (\delta + n – k – 2) – \delta (k + 2) (n – k – 2).\end{aligned}\]
Hence \(d(v) = \Delta\) for each \(v \in V – I\), \[\sum\limits_{i = 1}^{k + 2} d^2(u_i) + \delta (n – k – 2) \sum\limits_{i = 1}^{k + 2} 1^2 = (\delta + n – k – 2) \sum\limits_{i = 1}^{k + 2} d(u_i),\] and \(\sum\limits_{i = 1}^{k + 2}d(u_i) = e\). Thus \(\sum\limits_{v \in V – I}d(v) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\) and \(\Delta = d(v) \leq k + 2\), where \(v\) is any vertex in \(V – I\).
The remaining proofs are divided into two cases.
Case 1. \(\delta = n – k – 2\).
In this case, we have \(d(u) = \delta\) for each \(u\) in \(I\). Thus \(\delta (k + 2) = |E(I, V – I)| = \Delta (n – k – 2) \geq \delta (n – k – 2)\). Thus \(n \leq 2 k + 4\). Since \(n \geq 2 k + 2\), we have \(n = 2 k + 4\), \(n = 2 k + 3\), or \(n = 2 k + 2\). If \(n = 2 k + 4\), then \(k \geq 3\) since \(n \geq 9\). Notice now that \(|I| = |V – I| = k + 2\). From Lemma 4, we have that \(G\) is Hamiltonian and thereby \(G\) is traceable, a contradiction. If \(n = 2 k + 3\), Since \(n \geq 9\), then \(k \geq 3\). From Lemma 5, we have that \(G\) has a cycle of length at least \((n – 1)\) and thereby \(G\) is traceable, a contradiction. If \(n = 2 k + 2\), then \(G\) is \(K_{k, \, k + 2}\).
Case 2. \(\delta < n – k – 2\).
In this case, we, from Lemma 3, have that \(I = P \cup Q\), where \(P = \{\, x : x \in I, d(x) = n – k – 2 \,\}\) and \(Q = \{\, y : y \in I, d(y) = \delta \,\}\). If \(|P| > 0\), then there exists a vertex \(z\) in \(I\) such that \(d(z) = n – k – 2\). Thus \(n – k – 2 = d(z) \leq \Delta \leq k + 2\). Thus \(n \leq 2 k + 4\). Since \(n \geq 2 k + 2\), we have \(n = 2 k + 4\), \(n = 2 k + 3\), or \(n = 2 k + 2\). If \(n = 2 k + 4\), then \(k \geq 3\) since \(n \geq 9\). Notice now that \(|I| = |V – I| = k + 2\). We, from Lemma 4, have that \(G\) is Hamiltonian and thereby \(G\) is traceable, a contradiction. If \(n = 2 k + 3\), then \(k \geq 3\) since \(n \geq 9\). We, from Lemma 5, have that \(G\) has a cycle of length at least \((n – 1)\) and thereby \(G\) is traceable, a contradiction. If \(n = 2 k + 2\), then \(G\) is \(K_{k, \, k + 2}\). Thus \(n – k – 2 = k = \delta\), a contradiction again. If \(|P| = 0\), then all the vertices in \(I\) have a degree of \(\delta\). Therefore \(\delta (k + 2) = |E(I, V – I)| = \Delta (n – k – 2) \geq \delta (n – k – 2)\). Thus \(n \leq 2 k + 4\). Since \(n \geq 2 k + 2\), we have \(n = 2 k + 4\), \(n = 2 k + 3\), or \(n = 2 k + 2\). Repeating the arguments above, we can reach a contradiction for each of the three cases of \(n = 2 k + 4\), \(n = 2 k + 3\), or \(n = 2 k + 2\).
This completes the proof of Theorem 2. ◻
Before we present the proof of Theorem 3, let us recall Theorem 3.
Suppose \(G\) is a graph with \(n\) vertices and \(e\) edges. If the minimum degree \(\delta\) of \(G\) is at least \(1\), then \[Z_1(G) \leq (n – \beta)\Delta^2 + e (\delta + n
– \beta) – \delta \beta (n – \beta)\] with equality if and only
if \(G\) is \(K_{\beta, \, n – \beta}\) or \(G\) is a bipartite graph with partition
sets of \(I\) and \(V – I\) such that \(|I| = \beta\), \(\delta < n – \beta\), \(d(v) = \Delta\) for each vertex \(v\) in \(V –
I\), and \(I = P \cup Q\), where
\(P = \{\, x : x \in I, d(x) = n – \beta
\,\}\), \(Q = \{\, y : y \in I, d(y) =
\delta \,\}\), where \(\Delta\)
is the maximum degree of \(G\).
Proof of Theorem 3. Let \(G\) be a graph with \(n\) vertices, \(e\) edges, and \(\delta \geq 1\). Clearly, \(\beta < n\). Let \(I := \{\, u_1, u_2, …, u_{\beta} \,\}\) be a maximum independent set in \(G\). Clearly, \[\sum\limits_{v \in V – I} d(v) \geq |E(I, V – I)| \geq \sum\limits_{u \in I} d(u).\]
Since \(2e = \sum\limits_{v \in V – I} d(v) + \sum\limits_{u \in I} d(u)\), we have that \[\sum\limits_{v \in V – I} d(v) \geq e \geq \sum\limits_{u \in I} d(u).\]
Obviously, \(0 < \delta \leq d(u) \leq n – \beta\) for each \(u \in I\). Applying Lemma 3 with \(s = \beta\), \(a_i = 1\) and \(b_i = d(u_i)\) with \(i = 1, 2, … , \beta\), \(m_1 = 1 > 0\), \(M_1 = 1\), \(m_2 = \delta > 0\), and \(M_2 = n – \beta\), we have \[\sum\limits_{i = 1}^{\beta} d^2(u_i) + \delta (n – \beta) \sum\limits_{i = 1}^{\beta} 1^2 \leq (\delta + n – \beta)\sum\limits_{i = 1}^{\beta} d(u_i) \leq (\delta + n – \beta) e.\]
Thus \[\sum\limits_{i = 1}^{\beta} d^2(u_i) \leq e (\delta + n – \beta) – \delta (n – \beta)\beta.\]
Therefore \[Z_1 = \sum\limits_{v \in V – I} d^2(v) + \sum\limits_{u \in I} d^2(u) \leq (n – \beta)\Delta^2 + e (\delta + n – \beta) – \delta \beta (n – \beta).\]
If \[Z_1 = \sum\limits_{v \in V – I} d^2(v) + \sum\limits_{u \in I} d^2(u) = (n – \beta)\Delta^2 + e (\delta + n – \beta) – \delta \beta (n – \beta),\]
then \(d(v) = \Delta\) for each \(v \in V – I\), \[\sum\limits_{i = 1}^{\beta} d^2(u_i) + \delta (n – \beta) \sum\limits_{i = 1}^{\beta} 1^2 = (\delta + n – \beta) \sum\limits_{i = 1}^{\beta} d(u_i),\] and \(\sum\limits_{i = 1}^{\beta}d(u_i) = e\). Thus \(\sum\limits_{v \in V – I}d(v) = e\) and \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\) and \(\Delta = d(v) \leq \beta\), where \(v\) is any vertex in \(V – I\).
The remaining proofs are divided into two cases.
Case 1. \(\delta = n – \beta\).
In this case, we have \(d(u) = \delta\) for each \(u\) in \(I\). Thus \(G\) is \(K_{\beta, \, n – \beta}\).
Case 2. \(\delta < n – \beta\).
In this case, we, from Lemma 3, have that \(I = P \cup Q\), where \(P = \{\, x : x \in I, d(x) = n – \beta \,\}\) and \(Q = \{\, y : y \in I, d(y) = \delta \,\}\). Thus \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \beta\), \(\delta < n – \beta\), \(d(v) = \Delta\) for each vertex \(v\) in \(v – I\), and \(I = P \cup Q\), where \(P = \{\, x : x \in I, d(x) = n – \beta \,\}\), \(Q = \{\, y : y \in I, d(y) = \delta \,\}\).
Suppose \(G\) is \(K_{\beta, \, n – \beta}\). Since \(V – I\) is independent, \(n – \beta = |V – I| \leq \beta\). Thus \(\delta = n – \beta\), \(\Delta = \beta\), and \(e = \beta (n – \beta)\). A simple computation can verify that \[Z_1 = (n – \beta)\Delta^2 + e (\delta + n – \beta) – \delta \beta (n – \beta).\]
Suppose \(G\) is a bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \beta\), \(\delta < n – \beta\), \(d(v) = \Delta\) for each vertex \(v\) in \(v – I\), and \(I = P \cup Q\), where \(P = \{\, x : x \in I, d(x) = n – \beta \,\}\), \(Q = \{\, y : y \in I, d(y) = \delta \,\}\). Then \(P \cap Q = \emptyset\), \(\beta = |I| = |P| + |Q|\), and \(e = |P|(n – \beta) + |Q| \delta\). Thus \[\begin{aligned}(n – \beta)\Delta^2 + e (\delta + n – \beta) – \delta \beta (n – \beta)&= (n – \beta)\Delta^2 + (|P|(n – \beta) + |Q| \delta)(\delta + n – \beta) – \delta \beta (n – \beta)\\ &= (n – \beta)\Delta^2 + |P| (n – \beta)^2 + |Q| \delta^2 + \delta (|P| + |Q|) (n – \beta) – \delta \beta (n – \beta)\\ &= (n – \beta)\Delta^2 + |P| (n – \beta)^2 + |Q| \delta^2\\ & = \sum\limits_{v \in V – I} d^2(v) + \sum\limits_{u \in I} d^2(u) = Z_1.\end{aligned}\]
This completes the proof of Theorem 3. ◻
Bondy, J. A., & Murty, U. S. R. (1976). Graph Theory With Applications (Vol. 290). London: Macmillan.
Gould, R. J. (2014). Recent advances on the Hamiltonian problem: Survey III. Graphs and Combinatorics, 30, 1-46.
Gould, R. J. (2003). Advances on the Hamiltonian problem–a survey. Graphs and Combinatorics, 19(1), 7-52.
Gould, R. J. (1991). Updating the Hamiltonian problem—a survey. Journal of Graph Theory, 15(2), 121-157.
Gutman, I., & Trinajstić, N. (1972). Graph theory and molecular orbitals. Total \(\phi\)-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4), 535-538.
Gutman, I., Trinajstić, N., & Wilcox, C. F. (1975). Graph theory and molecular orbitals. XII. Acyclic polyenes. Journal of chemical physics, 62(9), 3399-3405.
Borovicanin, B., Das, K. C., Furtula, B., & Gutman, I. (2017). Bounds for Zagreb Indices. Match (Mülheim an der Ruhr, Germany) 78, 17-100.
Gutman, I., Furtula, B., Das, K. C., Milovanovic, E., & Milovanovic, I. Zagreb Indices: Bounds and Extremal Graphs. Bounds in Chemical Graph Theory–Basics, 67-153.
Gutman, I., & Das, K. C. (2004). The first Zagreb index 30 years after. MATCH Communications in Mathematical and in Computer Chemistry, 50(1), 83-92.
Jin, Y., Zhou, S., Tian, T., & Das, K. C. (2024). Sufficient conditions for hamiltonian properties of graphs based on the difference of Zagreb indices. Computational and Applied Mathematics, 43(6), 385.
Li, R. (2024). The general first Zagreb index conditions for Hamiltonian and traceable graphs. Discrete Mathematics Letter, 14, 31-35.
An, M. (2022). The first Zagreb index, reciprocal degree distance and Hamiltonian-connectedness of graphs. Information Processing Letters, 176, 106247.
Li, R. (2024). The first general Zagreb index and some Hamiltonian properties of graphs. Math. Asp. Topol. Indices, 6, 43-48.
Jahanbani, A., & Sheikholeslam, S. (2023). The topological indices and some Hamiltonian properties of graphs. Applied Mathematics E-Notes, 23, 260-264.
Lu, Y., & Zhou, Q. (2022). On hyper-Zagreb index conditions for Hamiltonicity of graphs. Czechoslovak Mathematical Journal, 72(3), 653-662.
Su, G., Li, Z., & Shi, H. (2020). Sufficient conditions for a graph to be k-edge-hamiltonian, k-path-coverable, traceable and Hamilton-connected. The Australasian Journal of Combinatorics, 77, 269-284.
Li, R. (2019). The hyper-Zagreb index and some Hamiltonian properties of graphs. Discrete Mathematics Letters 1, 54-58.
Li, R., & Taylor, M. M. (2017). 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.
Diaz, J. B., & Metcalf, F. T. (1964). Complementary inequalities I: Inequalities complementary to Cauchy’s inequality for sums of real numbers. Journal of Mathematical Analysis and Applications, 9(1), 59-74.
Chvátal, V., & Erdös, P. (1972). A note on Hamiltonian circuits. Discrete Mathematics, 2(2), 111-113.
Moon, J., & Moser, L. (1963). On Hamiltonian bipartite graphs. Israel Journal of Mathematics, 1, 163-165.
Jackson, B. (1985). Long cycles in bipartite graphs. Journal of Combinatorial Theory, Series B, 38(2), 118-131.
