Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

The first Zagreb index, the algebraic connectivity and some Hamiltonian properties of graphs

Rao Li1
1Department of Computer Science, Engineering and Mathematics, University of South Carolina Aiken Aiken, SC 29801, USA
  • Received: 29/10/2025
  • Revised: 01/12/2025
  • Accepted: 10/12/2025
  • Published Online: 14/02/2026

Abstract

The first Zagreb index of a graph \(G\) is defined as \(\sum\limits_{u \in V} d_G^2(u)\), where \(d_G(u)\) is the degree of vertex \(u\) in \(G\). The algebraic connectivity of a graph \(G\) is defined as the second smallest eigenvalue of the Laplacian matrix of \(G\). Using Wagner’s inequality, we in this paper first obtain an upper bound for the algebraic connectivity that involves the first Zagreb index of a graph. Following the ideas of obtaining the upper bound, we present sufficient conditions involving the first Zagreb index and the algebraic connectivity for some Hamiltonian properties of graphs.

Keywords: first Zagreb index, algebraic connectivity, Hamiltonian graph, traceable graph

1. Introduction

We consider only finite undirected graphs without loops or multiple edges. Notation and terminology not defined in this paper follow those in [3]. Let \(G = (V(G), E(G))\) be a graph. We use \(n\) and \(e\) to denote the number of vertices and the number of edges in \(G\), respectively. The complement of \(G\) is denoted by \(G^c\). The degree of a vertex \(u\) in \(G\) is represented by \(d_G(u)\). We use \(\delta = d_1 \leq d_2 \leq \cdots \leq d_n = \Delta\) to denote the degree sequence of a graph \(G\). We use \(K_{p}\) to denote a complete graph of order \(p\). A subset of \(V(G)\) in a graph \(G\) is an independent set if any two vertices in the subset are not adjacent. An independent set in a graph \(G\) is called a maximum independent set if its size is as large as possible. The independence number, denoted \(\beta(G)\), of a graph \(G\) is defined as the size of a maximum independent set in \(G\). For two disjoint vertex subsets \(A\) and \(B\) of \(V(G)\), we define \(E(A, B)\) as the set of all the edges in \(E(G)\) such that one end vertex of each edge is in \(A\) and another end vertex of the edge is in \(B\). Namely, \(E(A, B) := \{\, e : e = ab \in E, a \in A, b \in B \,\}\).

The Laplacian matrix of a graph \(G\), denoted \(L(G)\), is defined as \(D(G)- A(G)\), where \(D(G)\) is the diagonal matrix \(diag(d_1, d_2, …, d_n)\) of \(G\) and \(A(G)\) is the adjacency matrix of \(G\). We use \(0 = \lambda_1(G) \leq \lambda_2(G) \leq \cdots \leq \lambda_n(G)\) to denote the eigenvalues of \(L(G)\). The concept of the algebraic connectivity of a graph \(G\) was introduced by [9] and it was defined as \(\lambda_2(G)\). The algebraic connectivity is very important concept in spectral graph theory. Some results on the algebraic connectivity can be found in[1], [6], [8],[15], [16], and [23]. The first Zagreb index of a graph was introduced by Gutman and Trinajstić in [13]. See also [12]. For a graph \(G\), its first Zagreb index, denoted \(Z_1(G)\), is defined as \(\sum\limits_{u \in V(G)} d_G^{2}(u)\). The first Zagreb index is one of the most important topological indices of a graph. Many results on the first Zagreb index of a graph can be found in the survey paper [4] and the references therein. A cycle \(C\) in a graph \(G\) is a Hamilton cycle of \(G\) if all the vertices of \(G\) are on \(C\). A graph \(G\) is called Hamiltonian if \(G\) contains a Hamilton cycle. A path \(P\) in a graph \(G\) is a Hamilton path of \(G\) if all the vertices of \(G\) are on \(P\). A graph \(G\) is called traceable if \(G\) contains a Hamilton path.

Using Wagners inequality, we in this paper first obtain an upper bound for the algebraic connectivity that involves the first Zagreb index of a graph. Motivated by the first Zagreb index conditions for some Hamiltonian properties obtained in[2], [14], [18],[19],[17],[20],[22], and[21], we use the ideas of obtaining the upper bound to present new sufficient conditions involving the first Zagreb index and the algebraic connectivity for Hamiltonian graphs and traceable graphs. Below are the results of this paper.

Theorem 1.1. Let \(G\) be a connected graph with \(n \geq 2\) vertices and \(e\) edges. Suppose \(\beta\) is the independence number of \(G\) and \(\theta\) is real number with \(0 \leq \theta \leq 1\). Then \[\lambda_2(G) \leq \frac{n}{(n – \beta)} \sqrt{\frac{Z_1(G) – (n – \beta) \delta^2 + \theta \beta(\beta – 1)(n – \beta)^2}{\beta(1 + \theta (\beta – 1))}},\] with equality if and only if \(G\) is \(K_n\).

Theorem 1.2. Let \(G\) be a \(k\)-connected (\(k \geq 2\)) graph with \(n \geq 3\) vertices and \(e\) edges. Suppose \(\theta\) is real number with \(0 \leq \theta \leq 1\).

If \[\lambda_2(G) \geq \frac{n}{(n – k – 1)} \sqrt{\frac{Z_1(G) – (n – k – 1) \delta^2 + \theta (k + 1)k(n – k – 1)^2}{(k + 1)(1 + \theta k)}},\] then \(G\) is Hamiltonian.

Theorem 1.3. Let \(G\) be a \(k\)-connected (\(k \geq 1\)) with \(n\) vertices and \(e\) edges. Suppose \(\theta\) is real number with \(0 \leq \theta \leq 1\). If \[\lambda_2(G) \geq \frac{n}{(n – k – 2)} \sqrt{\frac{Z_1(G) – (n – k – 2) \delta^2 + \theta (k + 2)(k + 1)(n – k – 2)^2}{(k + 2)(1 + \theta (k + 1))}},\] then \(G\) is traceable.

2. Lemmas

We will use some existing results as our lemmas. Lemma 2.1 below is the Wagners inequality [25] (see also Theorem \(2.56\) on Page \(22\) in[7]) .

Lemma 2.1. [25] [7]. Let \(a_k\) and \(b_k\) (\(k = 1, 2, \cdots, s\)) be real numbers. Suppose \(\theta\) is a real number with \(0 \leq \theta \leq 1\). Then \[\left(\sum\limits_{k = 1}^s a_k b_k + \theta \sum\limits_{i \neq j} a_i b_j\right)^2 \leq \left(\sum\limits_{k = 1}^s a_k^2 + 2 \theta \sum\limits_{i < j} a_i a_j\right) \left(\sum\limits_{k = 1}^s b_k^2 + 2 \theta \sum\limits_{i < j} b_i b_j\right).\]

Lemma 2.2 is Proposition \(2.1\) on Page \(173\) in[24].

Lemma 2.2. [24]. Let G be a graph of order \(n\). For any nontrivial subset \(X\) of vertices of \(G\), \(X \neq \emptyset\), \(X \neq V(G)\), we have \[\lambda_2 \leq \frac{n |E(X, V – X)|}{|X| |V – X|}.\]

Lemma 2.3 below is Lemma 13.1.3 in [10].

Lemma 2.3. [10]. If \(G\) is a graph on \(n\) vertices and \(2 \leq i \leq n\), then \(\lambda_i(G^c) = n – \lambda_{n – i + 2}(G)\).

Lemma 2.4 below is Corollary \(2\) on Page \(224\) in[11].

Lemma 2.4. [11]. If a graph \(G\) has an edge, then \(\lambda_n(G) \geq \Delta + 1\).

The next two results are from[5].

Lemma 2.5. [5]. Let \(G\) be a \(k\)-connected graph of order \(n \geq 3\). If \(\beta \leq k\), then \(G\) is Hamiltonian.

Lemma 2.6. [5]. Let \(G\) be a \(k\)-connected graph of order n. If \(\beta \leq k + 1\), then \(G\) is traceable.

3. Proofs

Proof of Theorem 1.1. Let \(G\) be a connected graph with \(n \geq 2\) vertices and \(e\) edges. Suppose \(I := \{\, u_1, u_2, …, u_{\beta} \,\}\) is a maximum independent set in \(G\). Since \(n \geq 2\) and \(G\) is connected, we have that \(\beta < n\). Set \(V – I = \{\, v_1, v_2, …, v_{n – \beta} \,\}\). Thus \[\sum\limits_{u \in I} d(u) = |E(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).\] Notice that \(0 < \delta \leq d(u) \leq (n – \beta)\) for each \(u \in I\). Applying Lemma 2.1 with \(s = \beta\), \(a_i = d(u_i)\) and \(b_i = 1\) for each \(i = 1, 2, … , \beta\), we have that \[\begin{aligned} &\left(\sum\limits_{i = 1}^{\beta} d(u_i)*1 + \theta \sum\limits_{1 \leq i \neq j \leq \beta} d(u_i)*1\right)^2\\ &\quad\leq \left(\sum\limits_{i = 1}^{\beta} d^2(u_i) + 2 \theta \sum\limits_{1 \leq i < j \leq \beta} d(u_i)*d(u_j)\right) \left(\sum\limits_{i = 1}^{\beta} 1^2 + 2 \theta \sum\limits_{1 \leq i < j \leq \beta} 1* 1\right)\\ &\quad\leq \left(\sum\limits_{i = 1}^{\beta} d^2(u_i) + 2 \theta \sum\limits_{1 \leq i < j \leq \beta} d(u_i)*d(u_j)\right) \left(\beta + 2 \theta \, \frac{\beta (\beta – 1)}{2}\right)\\ &\quad\leq \left(\sum\limits_{i = 1}^{\beta} d^2(u_i) + 2 \theta \sum\limits_{1 \leq i < j \leq \beta} (n – \beta)*(n – \beta)\right) (\beta + \theta \beta (\beta – 1))\\ &\quad\leq \left(\sum\limits_{i = 1}^{\beta} d^2(u_i) + 2 \theta \, \frac{\beta (\beta – 1)}{2} (n – \beta)*(n – \beta)\right) (\beta + \theta \beta (\beta – 1))\\ &\quad\leq \left(\sum\limits_{i = 1}^{\beta} d^2(u_i) + \theta \beta(\beta – 1) (n – \beta)^2 \right) (\beta + \theta \beta(\beta – 1)). \end{aligned}\]

Thus \[\begin{aligned} \left(\sum\limits_{i = 1}^{\beta} d(u_i)\right)^2 \left(1 + \theta (\beta – 1)\right)^2=& \left(\sum\limits_{i = 1}^{\beta} d(u_i)*1 + \theta \sum\limits_{1 \leq i \neq j \leq \beta} d(u_i)*1\right)^2\\ \leq& \left(\sum\limits_{i = 1}^{\beta} d^2(u_i) + \theta \beta(\beta – 1)(n – \beta)^2 \right) (\beta + \theta \beta(\beta – 1)). \end{aligned}\]

Therefore \[\sum\limits_{i = 1}^{\beta} d(u_i) \leq \sqrt{\frac{\beta (\sum\limits_{i = 1}^{\beta} d^2(u_i) + \theta \beta(\beta – 1)(n – \beta)^2)}{(1 + \theta (\beta – 1))}}.\]

Since \[Z_1(G) = \sum\limits_{i = 1}^{\beta} d^2(u_i) + \sum\limits_{i = 1}^{n – \beta} d^2(v_i) \geq \sum\limits_{i = 1}^{\beta} d^2(u_i) + (n – \beta) \delta^2,\] we have that \[\sum\limits_{i = 1}^{\beta} d^2(u_i) \leq Z_1(G) – (n – \beta) \delta^2.\]

From Lemma 2.2, we have that \[\begin{aligned} \lambda_2(G) \leq& \frac{n |E(I, V – I)|}{|I| |V – I|} = \frac{n \sum\limits_{i = 1}^{\beta} d(u_i)}{\beta (n – \beta)}\\ \leq& \frac{n}{\beta(n – \beta)} \sqrt{\frac{\beta (\sum\limits_{i = 1}^{\beta} d^2(u_i) + \theta \beta(\beta – 1)(n – \beta)^2)}{(1 + \theta (\beta – 1))}}\\ \leq& \frac{n}{(n – \beta)} \sqrt{\frac{Z_1(G) – (n – \beta) \delta^2 + \theta \beta(\beta – 1)(n – \beta)^2}{\beta(1 + \theta (\beta – 1))}}. \end{aligned}\]

Suppose \[\lambda_2(G) = \frac{n}{(n – \beta)} \sqrt{\frac{Z_1(G) – (n – \beta) \delta^2 + \theta \beta(\beta – 1)(n – \beta)^2}{\beta(1 + \theta (\beta – 1))}}.\]

In reviewing of the proofs above, \[\begin{aligned} &\left(\sum\limits_{i = 1}^{\beta} d(u_i)*1 + \theta \sum\limits_{1 \leq i \neq j \leq \beta} d(u_i)*1\right)^2\\ &\qquad= \left(\sum\limits_{i = 1}^{\beta} d^2(u_i) + \theta \beta(\beta – 1) (n – \beta)^2 \right) (\beta + \theta \beta(\beta – 1)). \end{aligned}\]

This implies that \(d(u) = (n – \beta)\) for each \(u \in I\). We further have that \[Z_1(G) = \sum\limits_{i = 1}^{\beta} d^2(u_i) + \sum\limits_{i = 1}^{n – \beta} d^2(v_i) = \sum\limits_{i = 1}^{\beta} d^2(u_i) + (n – \beta) \delta^2.\]

This implies that \(d(v) = \delta\) for each \(v \in V – I\). Thus \[\begin{aligned} \lambda_2(G) =& \frac{n}{(n – \beta)} \sqrt{\frac{Z_1(G) – (n – \beta) \delta^2 + \theta \beta(\beta – 1)(n – \beta)^2}{\beta(1 + \theta (\beta – 1))}}\\ =& \frac{n}{(n – \beta)}\sqrt{\frac{\beta (n – \beta)^2 + \theta \beta(\beta – 1)(n – \beta)^2}{\beta(1 + \theta (\beta – 1))}} = n. \end{aligned}\]

From Lemma 2.3, we have that \(\lambda_n(G^c) = 0\). From Lemma 2.4, we have that \(G^c\) does not have any edge. Thus \(G\) is \(K_n\).

If \(G\) is \(K_n\), then a simple computation verifies that \[\lambda_2(G) = n = \frac{n}{(n – \beta)} \sqrt{\frac{Z_1(G) – (n – \beta) \delta^2 + \theta \beta(\beta – 1)(n – \beta)^2}{\beta(1 + \theta (\beta – 1))}}.\]

This completes the proof of Theorem 1.1. ◻

Note that \(\theta\) is a real number with \(0 \leq \theta \leq 1\). There are infinitely number of choices for the values of \(\theta\). Therefore Theorem 1.1 can give infinitely number of upper bounds involving the first Zagreb index for the algebraic connectivity of a graph.

Proof of Theorem 1.2. Let \(G\) be a \(k\)-connected (\(k \geq 2\)) graph with \(n \geq 3\) vertices and \(e\) edges satisfying the conditions in Theorem 1.2. Suppose \(G\) is not Hamiltonian. Then Lemma 2.5 implies that \(\beta \geq k + 1\). 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\). Set \(V – I = \{\, v_1, v_2, …, v_{n – k – 1} \,\}\). Using arguments which are similar to the corresponding portions in the proof of Theorem 1.1, we can show that \[\sum\limits_{u \in I} d(u) \leq e \leq \sum\limits_{v \in V – I} d(v).\]

Let \(s = (k + 1)\), \(a_i = d(u_i)\) and \(b_i = 1\) for each \(i = 1, 2, … , (k + 1)\) in Lemma 2.1. Using arguments which are similar to the corresponding portions in the proof of Theorem 1.1 again, we can show that \[\lambda_2(G) \leq \frac{n}{(n – k – 1)} \sqrt{\frac{Z_1(G) – (n – k – 1) \delta^2 + \theta (k + 1)k(n – k – 1)^2}{(k + 1)(1 + \theta k)}}.\]

From the given conditions in Theorem 1.2, we have that \[\lambda_2(G) = \frac{n}{(n – k – 1)} \sqrt{\frac{Z_1(G) – (n – k – 1) \delta^2 + \theta (k + 1)k(n – k – 1)^2}{(k + 1)(1 + \theta k)}}.\]

Using arguments which are similar to the corresponding portions in the proof of Theorem 1.1, we can show that \(G\) is \(K_n\), contradicting to \(\beta \geq k + 1 \geq 3.\)

This completes the proof of Theorem 1.2. ◻

Proof of Theorem 1.3. Let \(G\) be a \(k\)-connected (\(k \geq 1\)) graph with \(n\) vertices and \(e\) edges satisfying the conditions in Theorem 1.3. If \(n = 1\) or \(n = 2\), then it is clear that \(G\) is traceable. From now on we assume that \(n \geq 3\). Suppose \(G\) is not traceable. Then Lemma 2.6 implies that \(\beta \geq k + 2\). 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\). Set \(V – I = \{\, v_1, v_2, …, v_{n – k – 2} \,\}\). Using arguments which are similar to the corresponding portions in the proof of Theorem 1.1, we can show that \[\sum\limits_{u \in I} d(u) \leq e \leq \sum\limits_{v \in V – I} d(v).\]

Let \(s = (k + 2)\), \(a_i = d(u_i)\) and \(b_i = 1\) for each \(i = 1, 2, … , (k + 2)\) in Lemma 2.1. Using arguments which are similar to the corresponding portions in the proof of Theorem 1.1 again, we can also that \[\lambda_2(G) \leq \frac{n}{(n – k – 2)} \sqrt{\frac{Z_1(G) – (n – k – 2) \delta^2 + \theta (k + 2)(k + 1)(n – k – 2)^2}{(k + 2)(1 + \theta (k + 1))}}.\]

From the given conditions in Theorem 1.3, we have that \[\lambda_2(G) = \frac{n}{(n – k – 2)} \sqrt{\frac{Z_1(G) – (n – k – 2) \delta^2 + \theta (k + 2)(k + 1)(n – k – 2)^2}{(k + 2)(1 + \theta (k + 1))}}.\]

Using arguments which are similar to the corresponding portions in the proof of Theorem 1.1 we can show that \(G\) is \(K_n\), contradicting to \(\beta \geq k + 2 \geq 3.\)

This completes the proof of Theorem 1.3. ◻

References:

  1. N. Abreu. Old and new results on algebraic connectivity of graphs. Linear Algebra and its Applications, 423:53–73, 2007. https://doi.org/10.1016/j.laa.2006.08.017.
  2. M. An. The first Zagreb index, reciprocal degree distance and hamiltonian-connectedness of graphs. Information Processing Letters, 176:106247, 2022. https://doi.org/10.1016/j.ipl.2022.106247.
  3. J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Macmillan, London and Elsevier, New York, 1976.
  4. B. Borovićanin, K. Das, B. Furtula, and I. Gutman. Bounds for Zagreb indices. MATCH Communications in Mathematical and in Computer Chemistry, 78:17–100, 2017.
  5. C. Chvátal and P. Erdös. A note on hamiltonian circuits. Discrete Mathematics, 2:111–113, 1972. https://doi.org/10.1016/0012-365X(72)90079-9.
  6. K. Das. A conjecture on algebraic connectivity of graphs. Taiwanese Journal of Mathematics, 19:1317–1323, 2015. https://doi.org/10.1016/j.disc.2007.10.044.
  7. S. S. Dragomir. A survey on Cauchy–Bunyakovsky–Schwarz type discrete inequalities. Journal of Inequalities in Pure and Applied Mathematics, 4(3):Article 63, 2003. http://jipam.vu.edu.au/.
  8. S. Fallat, S. Kirkland, and S. Pati. On graphs with algebraic connectivity equal to minimum edge density. Linear Algebra and its Applications, 373:31–50, 2003. https://doi.org/10.1016/S0024-3795(02)00538-4.
  9. M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23:298–305, 1973.
  10. C. Godsil and G. Royle. Algebraic Graph Theory. Springer-Verlag, New York, 2001.
  11. R. Grone and R. Merris. The laplacian spectrum of a graph (ii). SIAM Journal on Discrete Mathematics, 7:221–229, 1994.
  12. I. Gutman, B. Ruščić, N. Trinajstić, and C. F. Wilcox. Graph theory and molecular orbitals. xii. acyclic polyenes. Journal of Chemical Physics, 62:3399–3405, 1975. https://doi.org/10.1063/1.430994.
  13. I. Gutman and N. Trinajstić. Graph theory and molecular orbitals: total π-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17:535–538, 1972. https://doi.org/10.1016/0009-2614(72)85099-1.
  14. A. Jahanbani and S. Sheikholeslam. The topological indices and some hamiltonian properties of graphs. Applied Mathematics E-Notes, 23:260–264, 2023. https://doi.org/10.4018/978-1-5225-9380-5.ch006.
  15. S. Kirkland. Algebraic connectivity. In L. Hogben et al., editors, Handbook of Linear Algebra, Discrete Mathematics and Its Applications, pages 36-1–36-12. Chapman and Hall/CRC, Boca Raton, 2007.
  16. S. Kirkland, I. Rocha, and V. Trevisan. Algebraic connectivity of k-connected graphs. Czechoslovak Mathematical Journal, 65:219–236, 2015. https://doi.org/10.1007/s10587-015-0170-9.
  17. R. Li. The first general Zagreb index and some hamiltonian properties of graphs. Mathematical Aspects of Topological Indices, 6:43–48, 2024.
  18. R. Li. The first Zagreb index and some hamiltonian properties of graphs. Mathematics, 12:3902, 2024. https://doi.org/10.3390/math12243902.
  19. 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.
  20. R. Li. The first Zagreb index conditions for hamiltonian and traceable graphs. Open Journal of Discrete Applied Mathematics, 8(2):45–51, 2025. https://doi.org/10.30538/psrp-odam2025.0115.
  21. R. Li. The first Zagreb index, the independence number and some hamiltonian properties of graphs. Open Journal of Discrete Mathematics, 15:92–99, 2025. https://doi.org/10.4236/ojdm.2025.154007.
  22. R. Li. The first Zagreb index, the laplacian spectral radius and some hamiltonian properties of graphs. Mathematics, 13(17):2897, 2025. https://doi.org/10.3390/math13172897.
  23. Z. Lin, R. Zhang, and J. Wang. Some new lower bounds on the algebraic connectivity of graphs. Contributions to Mathematics, 7:53–59, 2023. https://doi.org/10.47443/cm.2023.016.
  24. B. Mohar. Laplace eigenvalues of graphs – a survey. Discrete Mathematics, 109:171–183, 1992. https://doi.org/10.1016/0012-365X(92)90288-Q.
  25. S. S. Wagner. Notices. Notices of the American Mathematical Society, 12:220, 1965.
Citation
Rao Li. The first Zagreb index, the algebraic connectivity and some Hamiltonian properties of graphs[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 130. 89-96. https://doi.org/10.61091/jcmcc130-06.