On normalized Laplacian spectrum of zero divisor graphs of commutative ring Zⁿ

S. Pirzada, Bilal A. Rather, T. A. Chishti, U. Samee

Department of Mathematics, University of Kashmir, Srinagar, Kashmir, India

pirzadasd@kashmiruniversity.ac.in, bilalahmadrr@gmail.com, tachishti@uok.edu.in, drumatulsamee@gmail.com

For a finite commutative ring Zⁿ with identity 1 6= 0, the zero divisor graph Γ(Zn) is a simple connected graph having vertex set as the set of non-zero zero divisors, where two vertices x and y are adjacent if and only if xy = 0. We find the normalized Laplacian spectrum of the zero divisor graphs Γ(Zn) for various values of n and characterize n for which Γ(Zn) is normalized Laplacian integral. We also obtain bounds for the sum of graph invariant S ∗ β (G)-the sum of the β-th power of the non-zero normalized Laplacian eigenvalues of Γ(Zn).

Keywords: normalized Laplacian matrix, normalized Laplacian spectrum, zero divisor graph

Mathematics Subject Classification: 05C50, 05C12, 15A18

DOI: 10.5614/ejgta.2021.9.2.7

1. Introduction

In this paper, we consider only connected, simple and finite graphs. A graph is denoted by G(V (G), E(G)), where V (G) = {v1, v2, . . . , vn} is its vertex set and E(G) is its edge set. The order of G is |V (G)| = n and its size is |E(G)| = m. The set of vertices adjacent to v ∈ V (G), denoted by N(v), refers to the neighborhood of v. The degree of v, denoted by dG(v) (we simply write d^v if it is clear from the context) means the cardinality of N(v). A graph is called regular if each of its vertices has the same degree. The adjacency matrix A = (aij ) of G is a (0, 1)-square matrix of order n whose (i, j)-entry is equal to 1, if vⁱ is adjacent to v^j and equal to 0, otherwise. Let Deg(G) = diag(d1, d2, . . . , dn) be the diagonal matrix of vertex degrees

Received: 31 January 2020, Revised: 23 March 2021, Accepted: 1 April 2021.

\(d_i = d_G(v_i)\), \(i = 1, 2, \ldots, n\) associated to G. The matrices L(G) = Deg(G) - A(G) and Q(G) = Deg(G) + A(G) are respectively the Laplacian and the signless Laplacian matrices and their spectrum are respectively the Laplacian spectrum and signless Laplacian spectrum of the graph G. These matrices are real symmetric and positive semi-definite and are well studied.

The normalized Laplacian introduced by Chung [7] to study random walks, is denoted by \(\mathcal{L}(G)\) and is defined as \(\mathcal{L}(G) = Deg(G)^{-\frac{1}{2}}L(G)Deg(G)^{-\frac{1}{2}} = I_n - \mathbf{R}_G\), where \(Deg(G)^{-\frac{1}{2}}\) is the diagonal matrix whose i-th diagonal entry is \(\frac{1}{\sqrt{d_i}}\). Note that \(\mathcal{L}(G)\) is real symmetric positive semidefinite matrix. We order the normalized Laplacian eigenvalues of \(\mathcal{L}(G)\) as \(0 = \lambda_1(\mathcal{L}) \leq \lambda_2(\mathcal{L}) \leq \cdots \leq \lambda_n(\mathcal{L}) = 2\). In certain situations normalized Laplacian is a natural tool that works better than adjacency and Laplacian matrices. More literature about \(\mathcal{L}(G)\) can be found in [5, 10] and references therein.

The degree Kirchhoff index [9] of a graph is defined as

\[Kf^*(G) = \sum_{v_i, v_j \subseteq V(G)} d(v_i)d(v_j)R(v_i, v_j),\]

where \(R(v_i, v_j)\) is the effective resistance distance between the vertices \(v_i\) and \(v_j\) in an electrical network.

Burcu and Durmuş [3] defined the graph invariant \(S^*_{\beta}(G)\)-the sum of the \(\beta\)-th power of the non-zero normalized Laplacian eigenvalues of a connected graph G as

\[S_{\beta}^*(G) = \sum_{i=1}^h \lambda_i^{\beta},\]

where h is the number of non zero normalized Laplacian eigenvalues of G. If \(\beta=0\), we get \(S_0^*(G)=n\) and for \(\beta=1\), we have \(S_1^*(G)=Tr(\mathcal{L}(G))=n\). To avoid trivialities, we assume \(\beta\neq 0,1\), in particular for \(\beta=-1\), we obtain \(S_{-1}^*(G)=\sum_{i=1}^n\frac{1}{\lambda_i}\). This implies that \(2mS_{-1}^*(G)=Kf^*(G)\), where \(Kf^*(G)=2m\sum_{i=1}^{n-1}\frac{1}{\lambda_i}\) is the degree Kirchhoff index of G. The general Randić index of G, denoted by \(R_{\beta}(G)\), is defined by \(R_{\beta}(G)=\sum_{v_i\sim v_j}(d(v_i)d(v_j))^{\beta}\). Since \(S_2^*=Trace(\mathcal{L}^2)\), so the relation between \(S_{\beta}^*(G)\) and \(R_{\beta}(G)\) as given in [20] is

\[S_2^*(C) = n + 2\sum_{v_i \sim v_j} \frac{1}{d(v_i)d(v_j)} = n + 2R_{-1}(G).\]

For more information about \(R_{-1}(G)\) and its importance to the normalized Laplacian eigenvalues, see [5] and references therein.

Let R be a commutative ring with multiplicative identity \(1 \neq 0\). A non-zero element \(x \in R\) is called a zero divisor of R if there exists a non-zero \(y \in R\) such that xy = 0. The zero divisor graphs of commutative rings were first introduced by Beck [2]. In the definition he included the additive identity and was interested mainly in coloring of commutative rings. Later Anderson and

Livingston [1] modified the definition of zero divisor graphs and excluded the additive identity of the ring in the zero divisor set. Zero divisor graph has vertex set as the set of non-zero zero divisors, in which two vertices x and y are joined by an edge if and only if xy = 0. The zero divisor graph is of order \(N = n - \phi(n) - 1\) and size M, where \(\phi\) is Euler's totient function. Some related results can be seen in [6, 13, 14, 15, 16, 17, 19].

If G is any graph, we write Spec(G) for the spectrum of G which contains its eigenvalues including multiplicities. We use standard notation, \(K_n, K_{a,b}\), for complete graph, bipartite graph. Other undefined notations and terminology can be found in [8, 11, 12].

The rest of the paper is organized as follows. In Section 2, we obtain the normalized Laplacian spectrum of the zero divisor graph \(\Gamma(\mathbb{Z}_n)\) for various values of \(n \in \{pq, p^2q, p^3, p^4\}\) and show that \(\Gamma(\mathbb{Z}_{pq})\) is normalized Laplacian integral. In Section 3, we find the bounds for \(S^*_{\beta}(G)\) and as consequences we obtain bounds for degree Kirchhoff index of \(\Gamma(\mathbb{Z}_n)\). We have used computational software Wolfram Mathematica for computing approximate eigenvalues and characteristic polynomials of various matrices.

2. The normalized Laplacian spectrum of \(\Gamma(\mathbb{Z}_n)\)

Definition 1. Let G(V, E) be a graph of order n having vertex set \(\{1, 2, ..., n\}\) and \(G_i(V_i, E_i)\) be disjoint graphs of order \(n_i\), \(1 \le i \le n\). The graph \(G[G_1, G_2, ..., G_n]\) is formed by taking the graphs \(G_1, G_2, ..., G_n\) and joining each vertex of \(G_i\) to every vertex of \(G_j\) whenever i and j are adjacent in G.

This graph operation \(G[G_1, G_2, \ldots, G_n]\) is also called generalized join graph operation [4] and G-join operation. If \(G = K_2\), the \(K_2\)-join is the usual join operation, namely \(G_1 \nabla G_2\). Herein we follow later name with notation \(G[G_1, G_2, \ldots, G_n]\) and call it G-join.

An integer d is called a proper divisor of n if d divides n, written as d|n, for 1 < d < n. Let \(d_1, d_2, \ldots, d_t\) be the distinct proper divisors of n. Let \(\Upsilon_n\) be the simple graph with vertex set \(\{d_1, d_2, \ldots, d_t\}\), in which two distinct vertices are connected by an edge if and only if \(n|d_id_j\). If the prime power factorization of \(n = p_1^{n_1} p_2^{n_2} \ldots p_r^{n_r}\), where \(r, n_1, n_2, \ldots, n_r\) are positive integers and \(p_1, p_2, \ldots, p_r\) are distinct prime numbers, the order of the \(\Upsilon_n\) is given by

\[|V(\Upsilon_n)| = \prod_{i=1}^r (n_i + 1) - 2.\]

This \(\Upsilon_n\) is connected [6] and plays a fundamental role in the present section. For \(1 \leq i \leq t\), we consider the sets \(A_{d_i} = \{x \in \mathbb{Z}_n : (x,n) = d_i\}\). We see that \(A_{d_i} \cap A_{d_j} = \phi\), when \(i \neq j\), implying that the sets \(A_{d_1}, A_{d_2}, \ldots, A_{d_t}\) are pairwise disjoint and partitions the vertex set of \(\Gamma(\mathbb{Z}_n)\) as \(V(\Gamma(\mathbb{Z}_n)) = A_{d_1} \cup A_{d_2} \cup \cdots \cup A_{d_t}\). From the definition of \(A_{d_i}\), a vertex of \(A_{d_i}\) is adjacent [6] to the vertex of \(A_{d_j}\) in \(\Gamma(\mathbb{Z}_n)\) if and only if n divides \(d_i d_j\), for \(i, j \in \{1, 2, \ldots, t\}\). The following result [19] gives the cardinality of \(A_{d_i}\).

Lemma 2.1. \[|A_{d_i}| = \phi\left(\frac{n}{d_i}\right)\], for \(1 \le i \le t\).

The next lemma [6] says that the induced subgraphs \(\Gamma(A_{d_i})\) of \(\Gamma(\mathbb{Z}_n)\) are either cliques or their complements.

Lemma 2.2. The following hold.

(i) For \(i \in \{1, 2, ..., t\}\), the induced subgraph \(\Gamma(A_{d_i})\) of \(\Gamma(\mathbb{Z}_n)\) on the vertex set \(A_{d_i}\) is either the complete graph \(K_{\phi(\frac{n}{d_i})}\) or its complement \(\overline{K}_{\phi(\frac{n}{d_i})}\). Indeed, \(\Gamma(A_{d_i})\) is \(K_{\phi(\frac{n}{d_i})}\) if and only if n divides \(d_i^2\).

(ii) For \(i, j \in \{1, 2, ..., t\}\) with \(i \neq j\), a vertex of \(A_{d_i}\) is adjacent to either all or none of the vertices in \(A_{d_i}\) of \(\Gamma(\mathbb{Z}_n)\).

The following lemma says that \(\Gamma(\mathbb{Z}_n)\) is a generalized join of certain complete graphs and null graphs.

Lemma 2.3. [6] Let \(\Gamma(A_{d_i})\) be the induced subgraph of \(\Gamma(\mathbb{Z}_n)\) on the vertex set \(A_{d_i}\) for \(1 \leq i \leq t\). Then \(\Gamma(\mathbb{Z}_n) = \Upsilon_n[\Gamma(A_{d_1}), \Gamma(A_{d_2}), \ldots, \Gamma(A_{d_t})]\).

The following important result [18] helps in computing normalized Laplacian eigenvalues of G-join of graphs. As an application of this result, we compute the normalized Laplacian spectrum of zero divisor graphs \(\Gamma(\mathbb{Z}_n)\).

Theorem 2.4. [18] Let G be a graph with no isolated vertices and \(V(G) = \{1, 2, ..., k\}\), and \(G_i\)'s be \(r_i\)-regular graphs of order \(n_i\) (i = 1, 2, ..., k). If \(G = G[G_1, G_2, ..., G_k]\), then normalized Laplacian spectrum can be computed as follows.

\[Spec_{\mathcal{L}}(G) = \left(\bigcup_{i=1}^{k} \left(\frac{N_i}{r_i + N_i} + \frac{r_i}{r_i + N_i} (Spec_{\mathcal{L}}(G_i) \setminus \{0\})\right)\right) \bigcup Spec(C_{\mathcal{L}}(G)),\]

where

\[N_{i} = \begin{cases} \sum_{j \in N_{G}(i)} n_{j}, & N_{G}(i) \neq \emptyset, \\ 0, & otherwise. \end{cases}\]

and

\[C_{\mathcal{L}}(G) = (c_{ij})_{k \times k} = \begin{cases} \frac{N_i}{r_i + N_i}, & i = j, \\ -\sqrt{\frac{n_i n_j}{(r_i + N_i)(r_j + N_j)}}, & ij \in E(G), \\ 0, & otherwise. \end{cases}\](1)

A graph G is said to be normalized Laplacian integral if all its normalized Laplacian eigenvalues are integers. The following proposition says when a G-join graph is normalized Laplacian integral, the proof of which follows trivially from Theorem 2.4.

Proposition 2.5. The G-join graph \(G[G_1, G_2, \ldots, G_k]\) is normalized Laplacian integral if and only if \(\frac{N_i}{r_i + N_i}, \frac{r_i}{r_i + N_i} \in \mathbb{Z}\) and matrix \(C_{\mathcal{L}}(G)\) is integral.

From Theorem 2.4, we observe that, if \(G_i \cong \overline{K}_i\), then \(\frac{N_i}{r_i + N_i} = 1\) and \(\frac{r_i}{r_i + N_i} = 0\). In this case, \(G = G[G_1, G_2, \dots, G_k]\) is integral if and only if the matrix \(C_{\mathcal{L}}(G)\) is integral.

Recall that \(\Gamma(\mathbb{Z}_n)\) is a complete graph if and only if \(n=p^2\) for some prime p. Further the normalized Laplacian spectrum of \(K_\omega\) and \(\overline{K}_\omega\) on \(\omega\) vertices are \(\{0, \left(\frac{\omega}{\omega-1}\right)^{[\omega-1]}\}\) and \(\{0^{[\omega]}\}\) respectively. By Lemma 2.2, \(\Gamma(A_{d_i})\) is either \(K_{\phi(\frac{n}{d_i})}\) or its complement \(\overline{K}_{\phi(\frac{n}{d_i})}\) for \(1 \leq i \leq t\). So, by Theorem 2.4, out of \(n-\phi(n)-1\) number of normalized Laplacian eigenvalues of \(\Gamma(\mathbb{Z}_n)\), \(n-\phi(n)-1-t\) of them are known. The remaining t normalized Laplacian eigenvalues of \(\Gamma(\mathbb{Z}_n)\) will count from the zeros of the characteristic polynomial of the matrix \(C_{\mathcal{L}}(G)\) in (1).

In the following example, we find the normalized Laplacian spectrum with the help of Theorem 2.4.

Example 1. Normalized Laplacian eigenvalues of \(\Gamma(\mathbb{Z}_{30})\).

Let n=30. Then 2,3,5,6,10 and 15 are the proper divisors of n and \(\Upsilon_n\) is the graph \(G_6:3\sim 10\sim 6\sim 5,\ 10\sim 15\sim 2\) and \(6\sim 15\). Applying Lemma 2.3, we have

\[\Gamma(\mathbb{Z}_{30}) = \Upsilon_{30}[\overline{K}_8, \overline{K}_4, \overline{K}_2, \overline{K}_4, \overline{K}_2, \overline{K}_2].\]

Since \(r_i = 0\) for \(1 \le i \le 6\) and \((N_1, N_2, N_3, N_4, N_5, N_6) = (2, 11, 3, 2, 14, 1)\), so by Theorem 2.4, the normalized Laplacian spectrum of \(\Gamma(\mathbb{Z}_{30})\) consists of eigenvalue 1 with multiplicity 15 and the remaining six eigenvalues are given by following matrix

\[\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & -\frac{2}{\sqrt{7}} \\ 0 & 1 & 0 & 0 & -\frac{2}{3} & 0 \\ 0 & 0 & 1 & -\sqrt{\frac{2}{5}} & 0 & 0 \\ 0 & 0 & -\sqrt{\frac{2}{5}} & 1 & -\frac{2}{3}\sqrt{\frac{2}{5}} & -\sqrt{\frac{2}{35}} \\ 0 & -\frac{2}{3} & 0 & -\frac{2}{3}\sqrt{\frac{2}{5}} & 1 & -\frac{1}{3\sqrt{7}} \\ -\frac{2}{\sqrt{7}} & 0 & 0 & -\sqrt{\frac{2}{35}} & -\frac{1}{3\sqrt{7}} & 1 \end{pmatrix}.\]

The approximated eigenvalues of above matrix are

\[\{1.91118, 1.79124, 1.44407, 0.533079, 0.320432, 0.\}\]

Now, we investigate the normalized Laplacian spectrum of \(\Gamma(\mathbb{Z}_n)\) for \(n \in \{pq, p^2q, p^3, p^4\}\) with the help of Theorems 2.4. Consider n = pq, where p and q, p < q, are primes. By Lemmas 2.2 and 2.3, we have

\[\Gamma(\mathbb{Z}_{pq}) = \Upsilon_{pq}[\Gamma(A_p), \Gamma(A_q)] = K_2[\overline{K}_{\phi(p)}, \overline{K}_{\phi(q)}] = \overline{K}_{\phi(p)} \nabla \overline{K}_{\phi(q)} = K_{\phi(p), \phi(q)}. \tag{2}\]

Lemma 2.6. The normalized Laplacian spectrum of Γ(Zn) is {0, 1 [p+q−2] , 2}.

Proof. Let n = pq, where p and q, p < q, are distinct primes. Then the proper divisors of n are p and q, so that Υpq is K2. Since r¹ = r² = 0 and (N1, N2) = (q − 1, p − 1), so by Theorem 2.4 and equation (2), the normalized Laplacian spectrum of Γ(Zn) consists of the eigenvalue 1 with multiplicity p + q − 4 and the remaining two eigenvalues are given by the matrix

\[\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}\].

Lemma 2.7. The normalized Laplacian spectrum of Γ(Z^{p 2}q) is

\[\left\{0, 1^{[p^2+pq-2p-1]}, \left(\frac{pq-1}{pq-2}\right)^{[p-2]}, x_1, x_2, x_3\right\}\]

where x¹ ≥ x² ≥ x³ are the non-zero zeros of the characteristic polynomial of the matrix CQ(P4).

Proof. Let n = p 2 q, where p and q are distinct primes. Since the proper divisors of n are p, q, pq, p² , so Υ^p 2q is the path P⁴ : q ∼ p ² ∼ pq ∼ p. By Lemma 2.3, we have

\[\Gamma(\mathbb{Z}_{p^2q}) = \Upsilon_{p^2q}[\Gamma(A_q), \Gamma(A_{P^2}), \Gamma(A_{pq}), \Gamma(A_p)] = P_4[\overline{K}_{\phi(p^2)}, \overline{K}_{\phi(q)}, K_{\phi(p)}, \overline{K}_{\phi(pq)}].\]

Now, by Theorem 2.4, ^N1 r1+N¹ = N² r2+N² = N⁴ r4+N⁴ = 1 and ^N3 r3+N³ = pq−p pq−2 . The normalized Laplacian spectrum of Γ(Z^{p 2}q) consists of the eigenvalue 1 with multiplicity p ² + pq − p − 1, the eigenvalue pq − 1 pq − 2 with multiplicity p − 2 and the remaining four eigenvalues are given by the matrix

\[C_Q(P_4) = \begin{pmatrix} 1 & -\sqrt{\frac{p^2-p}{p^2-1}} & 0 & 0 \\ -\sqrt{\frac{p^2-p}{p^2-1}} & 1 & -\sqrt{\frac{q-1}{(p-1)(pq-2)}} & 0 \\ 0 & -\sqrt{\frac{q-1}{(p-1)(pq-2)}} & \frac{pq-p}{pq-2} & -\sqrt{\frac{pq-p-q+1}{pq-2}} \\ 0 & 0 & -\sqrt{\frac{pq-p-q+1}{pq-2}} & 1 \end{pmatrix}.\]

For n = p 2 , we have the following proposition.

Proposition 2.8. Let n = p 2 , where p is any prime. Then the normalized Laplacian spectrum of Γ(Zn) is 0, p−1 p−2 [p−2] .

Proof. Since Γ(Z^{p 2} ) = Γ(Ap) is the complete graph Kp−1, the result follows.

Proposition 2.9. Let \(n = p^3\). Then the normalized Laplacian spectrum of \(\Gamma(\mathbb{Z}_n)\) is

\[\left\{0,1^{[p^2-p-1]}, \left(\frac{p^2-1}{p^2-2}\right)^{[p-2]}, \frac{2p^2-p-2}{p^2-2}\right\}.\]

Proof. Since the proper divisors of n are p and \(p^2\), so \(\Upsilon_n\) is \(K_2: p \sim p^2\). By Lemma 2.3

\[\Gamma(\mathbb{Z}_{p^3}) = \Upsilon_{p^3}[\Gamma(A_p), \Gamma(A_{p^2})] = K_2[\overline{K}_{\phi(p^2)}, \overline{K}_{\phi(p)}] = \overline{K}_{p(p-1)} \nabla K_{p-1}.\]

This implies that \(\Gamma(\mathbb{Z}_{p^3})\) is a complete split graph of order \(p^2-1\), having independent set of cardinality p(p-1) and clique of size p-1. By Theorem 2.4, we have \(\left(\frac{N_1}{r_1+N_1},\frac{N_2}{r_2+N_2}\right)=\left(1,\frac{p^2-p}{p^2-2}\right)\), \(\left(\frac{r_1}{r_1+N_1},\frac{r_2}{r_2+N_2}\right)=\left(0,\frac{p-2}{p^2-2}\right)\) and

\[C_{\mathcal{L}}(K_2) = \begin{pmatrix} 1 & -\sqrt{\frac{p^2-p}{p^2-2}} \\ -\sqrt{\frac{p^2-p}{p^2-2}} & \frac{p^2-p}{p^2-2} \end{pmatrix}.\]

Now, it is easy to see that the eigenvalues are 1 with multiplicity \(p^2-p-1\), the eigenvalue \(\frac{p^2-1}{p^2-2}\) with multiplicity p-2 and two more eigenvalues are given by matrix \(C_{\mathcal{L}}(K_2)\) which can be computed as \(\{0,\frac{2p^2-p-2}{p^2-2}\}\).

Proposition 2.10. If \(n = p^4\), then the normalized Laplacian spectrum of \(\Gamma(\mathbb{Z}_n)\) is

\[\left\{0,1^{[p^3-p^2-1]}, \left(\frac{p^3-1}{p^3-2}\right)^{[p-2]}, \left(\frac{p^2-1}{p^2-2}\right)^{[p^2-p-1]}, \frac{2p^5-6p^3-2p^2+6\pm\sqrt{D}}{2(p^5-2p^3-2p^2+4)}\right\},\]

where \(D = 4p^{10} - 8p^9 - 7p^8 + 8p^7 + 24p^6 - 40p^4 + 8p^3 + 8p^2 + 4\).

Proof. As proper divisors of n are \(p,p^2\) and \(p^3\), so \(\Upsilon_n\) is \(P_3:p\sim p^3\sim p^2\). By Lemmas 2.1, 2.2 and 2.3, \(\Gamma(A_p)=\overline{K}_{\phi(p^3)}=\overline{K}_{p^2(p-1)},\) \(\Gamma(A_{p^2})=K_{\phi(p^2)}=K_{p(p-1)},\) and \(\Gamma(A_{p^3})=K_{\phi(p)}=K_{p-1}.\) Therefore

\[\Gamma(\mathbb{Z}_{p^4}) = \Upsilon_{p^3}[\Gamma(A_p), \Gamma(A_{p^3}), \Gamma(A_{p^2})] = P_3[\overline{K}_{p^2(p-1)}, K_{p-1}, K_{p(p-1)}] = K_{p-1} \nabla (\overline{K}_{p^2(p-1)} \cup K_{p(p-1)}).\]

Thus, by Theorem 2.4, we have \(\left(\frac{N_1}{r_1+N_1}, \frac{N_2}{r_2+N_2}, \frac{N_3}{r_3+N_3}\right) = \left(1, \frac{p^3-p}{p^3-2}, \frac{p-1}{p^2-2}\right), \left(\frac{r_1}{r_1+N_1}, \frac{r_2}{r_2+N_2}, \frac{r_3}{r_3+N_3}\right) = \left(0, \frac{p-2}{p^3-2}, \frac{p^2-p-1}{p^2-2}\right)\) and

\[C_{\mathcal{L}}(P_3) = \begin{pmatrix} 1 & -\sqrt{\frac{p^3 - p^2}{p^3 - 2}} & 0\\ -\sqrt{\frac{p^3 - p^2}{p^3 - 2}} & \frac{p^2 - p}{p^3 - 2} & -\sqrt{\frac{(p-1)(p^2 - p)}{(p^2 - 2)(p^3 - 2)}}\\ 0 & -\sqrt{\frac{(p-1)(p^2 - p)}{(p^2 - 2)(p^3 - 2)}} & \frac{p - 1}{p^2 - 2} \end{pmatrix}.\]

This completes the proof.

As shown in [6], \(\Gamma(\mathbb{Z}_n)\) is Laplacian integral when \(n=p^z\) for every prime p and positive integer \(z\geq 2\). The answer is negative for normalized Laplacian matrix. If \(n=p^{2m}, m\geq 2\) or \(n=p^{2m+1}, m\geq 1\), then by Propositions 2.8, 2.9 and 2.10, \(\Gamma(\mathbb{Z}_n)\) is not normalized Laplacian integral. However, by Lemma 2.6, if n=pq, where p and q, p<q, are primes, then \(\Gamma(\mathbb{Z}_n)\) is normalized Laplacian integral.

Proposition 2.11. The zero divisor graph \(\Gamma(\mathbb{Z}_n)\) is normalized Laplacian integral if and only if n is a product of two distinct primes.

3. Bounds for \(S^*_{\beta}(G)\)

Let \(\Gamma(\mathbb{Z}_n)\) be the zero divisor graph with normalized Laplacian eigenvalues \(\lambda_1 \geq \lambda_2 \geq 1\)

\[\cdots \geq \lambda_n\]. For \(1 \leq k \leq n-1\), let \(M_k = \sum_{i=1}^k \lambda_i\), \(m_k = \sum_{i=0}^k \lambda_{n-i}\), \(\triangle = \prod_{i=1}^n d(v_i)\) and

\[P = 1 + \sqrt{\frac{2}{n(n-1)} \sum_{v_i \sim v_j} \frac{1}{d(v_i)d(v_j)}}.\]

We recall Schur's theorem stating that the spectrum of any positive definite symmetric matrix majorizes its main diagonal, so \(M_k \ge \sum_{i=1}^k 1 = k\), for \(1 \le k \le n-2\). This can be further improved as

\[\frac{M_k}{k} = \frac{\sum_{i=1}^k \lambda_i}{k} \ge \frac{\sum_{i=k+1}^{N-1} \lambda_i}{N-1-k} = \frac{N-M_k}{N-1-k},\]

which after simplification gives

\[M_k \ge \frac{Nk}{N-1}. (3)\]

We can easily verify that equality occurs if and only if \(n=p^2\), where p is prime. If \(\Gamma(\mathbb{Z}_n)\) is a bipartite graph, then as above, we have \(M_k \geq k+1\) with equality if n is the product of two distinct primes.

We need the following lemma to obtain an upper bound for \(M_k\).

Lemma 3.1. [8] Let G be a graph of order n > 2. Then

1. \[\lambda_1 = \lambda_2 = \cdots = \lambda_{n-1}\] if and only if \(G \cong K_n\).

2. \[\lambda_1 = 2\] and \(\lambda_2 = \lambda_3 = \cdots = \lambda_{n-1}\) if and only if \(G \cong K_{a,b}\).

Lemma 3.2. Let \(\Gamma(\mathbb{Z}_n)\) be a zero divisor graph of order N. Then

\[M_k \le \frac{Nk + \sqrt{k(N - 1 - k)[2(N - 1)R_{-1} - N]}}{N - 1} \tag{4}\]

with equality if and only if \(n = p^2\), where p is prime.

Proof. Using Cauchy-Schwartz's inequality, we have

\[(N - M_k)^2 = \left(\sum_{i=k+1}^{N-1} \lambda_i\right)^2 \le (N - 1 - k) \left(\sum_{i=k+1}^{N-1} \lambda_i^2\right)\]\[= (N - 1 - k) \left(N + 2R_{-1} - \sum_{i=1}^k \lambda_i^2\right)\]\[\le (N - 1 - k) \left(N + 2R_{-1} - \frac{M_k^2}{k}\right).\]

After making simplifications, we obtain

\[\frac{N-1}{K}M_k^2 - 2NM_k + N(k+1) - 2(N-1-k)R_{-1} \le 0.\]

Thus, (4) follows.

Assume that equality occurs in (4). Then all the above inequalities must be equalities. So λ¹ = λ² = · · · = λ^k and λk+1 = λk+2 = · · · = λn, that is, Γ(Zn) has exactly two distinct normalized Laplacian eigenvalues. So, by (1) of Lemma 3.1, n = p 2 . Similarly it is easy to check the equality other way round.

Proceeding as in above lemma, we have the following observation.

Lemma 3.3. Let Γ(Zn) be a zero divisor graph of order N. Then

\[m_k \ge \frac{Nk + \sqrt{k(N-1-k)[2(N-1)R_{-1}-N]}}{N}\]

with equality if and only if n = p 2 , where p is prime.

Letting k = 1 in Lemmas 3.2 and 3.3 and noting that M¹ = λ¹ and m¹ = λN−1, we obtain the upper bound for spectral radius and the lower bound for the smallest non-zero eigenvalue of Γ(Zn). If Γ(Zn) is bipartite, then proceeding as in Lemma 3.2 and using Lemma 3.1, we have the following result.

Lemma 3.4. Let Γ(Zn) be a bipartite zero divisor graph of order N. Then, for 1 ≤ k ≤ N − 2,

\[M_k \le k + 1 + \frac{\sqrt{2(k-1)(N-1-k)(N-2)(R_{-1}-1)}}{N-2}\]

with equality if and only if n = pq, where p and q are primes.

The following lemmas will be used in the sequel.

Lemma 3.5. [8] Let G be a graph of order n and size m. Then the number of spanning trees T of G are given by

\[T = \frac{\triangle}{M} \prod_{i=1}^{n-1} \lambda_i.\]

Lemma 3.6. [10] Let G be a graph with n vertices and normalized Laplacian eigenvalues \(\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n = 0\). Then

\[\lambda_1 \ge P \ge \frac{n}{n-1}\]

with equality if and only if G is complete graph.

The following result gives a lower bound for \(S_{\beta}^*\).

Theorem 3.7. Let \(\Gamma(\mathbb{Z}_n)\) be a zero divisor graph of order N > 2, size M and spanning trees T. Then

\[S_{\beta}^* \ge P^{\beta} + (N-2) \left(\frac{2MT}{\triangle P}\right)^{\frac{N}{N-2}},\]

equality occurs if and only if \(n = p^2\), where p is prime.

Proof. By applying the arithmetic-geometric mean inequality, we obtain

\[S_{\beta}^{*}(G) = \lambda_{1}^{\beta} + \sum_{i=2}^{N-1} \lambda^{\beta} \ge \lambda^{\beta} + (N-2) \left(\prod_{i=2}^{N-1} \lambda_{i}^{\beta}\right)^{\frac{1}{N-2}}\]\[= \lambda_{1}^{\beta} + (N-2) \left(\frac{2MT}{\Delta\lambda_{1}}\right)^{\frac{\beta}{N-2}},\]

with equality if and only if \(\lambda_2 = \lambda_3 = \cdots = \lambda_{N-1}\). Let \(f(x) = x^{\beta} + (N-2) \left(\frac{2MT}{\Delta x}\right)^{\frac{\beta}{N-2}}\). We can

easily see that f(x) is increasing for \(x \ge \left(\frac{2MT}{\Delta}\right)^{\frac{1}{N-2}}\) where \(\beta > 0\) or \(\beta < 0\). By Lemma 3.6 and arithmetic-geometric mean inequality, we have

\[\lambda_1 \ge P \ge \frac{N}{N-1} = \frac{\sum\limits_{i=1}^{N-1} \lambda_i}{N-1} \ge \left(\prod_{i=1}^{N-1} \lambda_i\right) \frac{1}{N-1} = \left(\frac{2MT}{\triangle}\right)^{\frac{1}{N-1}}.\]

Thus \(S^*_{\beta}(G) \ge f(P)\) and the result follows.

Equality holds if and only if \(\lambda_1 = P\) and \(\lambda_2 = \lambda_3 = \cdots = \lambda_{N-1}\), by Lemma 3.1, \(n = p^2\), where p is prime.

The next result is an immediate consequence of Theorem 3.7.

Corollary 3.8. Let \(\Gamma(\mathbb{Z}_n)\) be a zero divisor graph with \(N \geq 3\), M edges and T spanning trees. Then

\[Kf^*(\Gamma(\mathbb{Z}_n)) \ge \frac{2M}{P} + 2(N-2)M\left(\frac{\triangle P}{2MT}\right)^{\frac{1}{n-2}}\]

with equality if and only if \(n = p^2\), where p is prime.

Theorem 3.9. Let \(\Gamma(\mathbb{Z}_n)\) be a connected graph of order N > 2. (i) If \(\beta < 0\) or \(\beta > 1\), then

\[S_{\beta}^*(\Gamma(\mathbb{Z}_n)) \ge P^{\beta} + \frac{(N-P))^{\beta}}{(n-2)^{\beta-1}},\]

with equality if and only if n is prime power.

(ii) If \(0 < \beta < 1\), then

\[S_{\beta}^*(\Gamma(\mathbb{Z}_n)) \le P^{\beta} + \frac{(N-P))^{\beta}}{(n-2)^{\beta-1}},\]

with equality if and only if n is prime power.

Proof. For \(\beta \neq 0, 1\) and x > 0, we can see that \(x^{\beta}\) is concave up when \(\beta < 0\) or \(\beta > 1\). Thus, by Jensen's inequality, we have

\[\left(\sum_{i=2}^{N-1} \frac{1}{N-2} \lambda_i\right)^{\beta} \le \sum_{i=2}^{N-1} \frac{1}{N-2} \lambda_i^{\beta},\]

which implies

\[\sum_{i=2}^{N-1} \lambda_i^{\beta} \ge \frac{1}{(N-2)^{\beta-1}} \left(\sum_{i=2}^{N-2} \lambda_i\right)^{\beta}\]

with equality if and only if \(\lambda_2 = \lambda_3 = \cdots = \lambda_{N-1}\). Now, using this information in the definition of \(S^*_{\beta}(G)\), we have

\[S_{\beta}^{*}(\Gamma(\mathbb{Z}_n)) \ge \lambda_1^{\beta} + \frac{1}{(N-2)^{\beta}} \left(\sum_{i=2}^{N-1} \lambda_i\right)^{\beta} = \lambda_1^{\beta} + \frac{(N-\lambda_1)^{\beta}}{(N-2)^{\beta-1}}.\]

Let \(f(x) = x^{\beta} + \frac{(N-x)^{\beta}}{(N-2)^{\beta-1}}\). By solving \(f'(x) \ge 0\), we see that f(x) is increasing for \(x \ge \frac{N}{N-1}\).

By Lemma 3.6, \(\lambda_1 \geq P \geq \frac{N}{N-1}\) and thus \(S_{\beta}^*(\Gamma(\mathbb{Z}_n)) \geq f(P) = P^{\beta} + \frac{(N-P))^{\beta}}{(n-2)^{\beta-1}}\) with equality if and only if \(\lambda_2 = \lambda_3 = \cdots = \lambda_{N-1}\) and \(\lambda_1 = P\). Therefore, by Lemma 3.1, \(\Gamma(\mathbb{Z}_n)\) is a complete graph with \(n = p^2\).

(ii) Assume that \(0 < \beta < 1\). Then we note that \(x^{\beta}\) is concave down when x > 0 or \(0 < \beta < 1\). So,

\[\left(\sum_{i=2}^{N-1} \frac{1}{N-2} \lambda_i\right)^{\beta} \ge \sum_{i=2}^{N-1} \frac{1}{N-2} \lambda_i^{\beta},\]

with equality if and only if \(\lambda_2 = \lambda_3 = \cdots = \lambda_n\) and f(x) is decreasing for \(x \ge \frac{N}{N-1}\). Now proceeding as in part (i) we obtain the required result.

From Theorem 3.9 (i), we have the following observation.

Corollary 3.10. Let Γ(Zn) be a connected graph of order N > 2. Then

\[Kf^*(\Gamma(\mathbb{Z}_n)) \ge \frac{2M}{P} + \frac{2(N-2)^2M}{(n-P)},\]

with equality if and only if n is prime power.

Theorem 3.11. Let Γ(Zn) be a zero divisor graph of order N ≥ 2 and 1 ≤ k ≤ N − 2 be a positive integer.

(i) If 0 < β < 1, then

\[S_{\beta}^{*}(\Gamma(\mathbb{Z}_n)) \le k^{1-\beta} \left(\frac{Nk}{N-1}\right)^{\beta} + (N-1-k) \left(\frac{N}{N-1}\right)^{\beta},\]

with equality if and only if n = p 2 .

(ii) If β > 1, then

\[S_{\beta}^{*}(\Gamma(\mathbb{Z}_n)) \ge k^{1-\beta} \left(\frac{Nk}{N-1}\right)^{\beta} + (N-1-k) \left(\frac{N}{N-1}\right)^{\beta},\]

with equality if and only if n = p 2 .

(iii) If β < 0, then

\[S_{\beta}^*(\Gamma(\mathbb{Z}_n)) \le k^{1-\beta} \left( \frac{Nk + \sqrt{\theta}}{N-1} \right)^{\beta} + (N-1-k)^{1-\beta} \left( \frac{N(N-1-k) - \sqrt{\theta}}{N-1} \right)^{\beta},\]

where θ = k(N − 1 − k)(2(N − 1)R⁻¹ − 2). Equality is attained if and only if n = p 2 .

Proof. By power mean inequality with 0 < β < 1, we have

\[\left(\sum_{i=1}^k \lambda_i^{\beta}\right)^{\frac{1}{\beta}} \le \frac{M_k}{k},\]

that is, P k i=1 λ β ⁱ ≤ k ¹−^βM β ^k with equality if and only if λ¹ = λ² = · · · = λk.

Similarly, N P−1 i=k+1 λ β ⁱ ≤ (N − 1 − k) 1−β (N − Mk) β , with equality if and only if λk+1 = λk+2 = · · · = λN−1.

Thus,

\[S_{\beta}^{*}(\Gamma(\mathbb{Z}_{n})) = \sum_{i=1}^{k} \lambda_{i}^{\beta} + \sum_{i=k+1}^{N-1} \lambda_{i}^{\beta} \le k^{1-\beta} M_{k}^{\beta} + (N-1-k)^{1-\beta} (N-M_{k})^{\beta}.\]

Consider the function

\[f(x) = k^{1-\beta} x^{\beta} + (N-1-k)^{1-\beta} (N-x)^{\beta}, \quad x \ge \frac{Nk}{N-1}.\]

We see that f(x) is a decreasing function for \(x \ge \frac{Nk}{N-1}\) provided \(0 < \beta < 1\). Therefore, by equation (3), \(M_k \ge \frac{Nk}{N-1}\), and we have

\[S_{\beta}^*(\Gamma(\mathbb{Z}_n)) = f(M_k) \le f\left(\frac{Nk}{N-1}\right) = k^{1-\beta} \left(\frac{Nk}{N-1}\right)^{\beta} + (N-1-k) \left(\frac{N}{N-1}\right)^{\beta}.\]

Assume that equality holds, then all the above inequalities must be equalities. That is, \(\lambda_1=\lambda_2=\cdots=\lambda_k\) and \(\lambda_{k+1}=\lambda_{k+2}=\cdots=\lambda_{N-1}\) and \(M_k=\frac{Nk}{N-1}\). From this, we have \(\lambda_1=\lambda_2=\cdots=\lambda_n=\frac{N}{N-1}\), which by Lemma 3.1, happens only if \(n=p^2\).

Conversely, we can easily verify that equality occurs if \(n = p^2\).

(ii) For \(\beta > 1\), using power mean inequality as in part (i), we obtain

\[S_{\beta}^*(\Gamma(\mathbb{Z}_n)) \ge k^{1-\beta} M_k^{\beta} + (N-1-k)^{1-\beta} (N-M_k)^{\beta}.\]

Also, \(f(x)=k^{1-\beta}x^{\beta}+(N-1-k)^{1-\beta}(N-x)^{\beta}, \quad x\geq \frac{Nk}{N-1}\) is an increasing function on \(x\geq \frac{Nk}{N-1}\) for \(\beta>1\). Now proceeding as in (i) we get (ii). Also, equality can be discussed similarly as in (i). (iii) We note that \(F(x)=k^{1-\beta}x^{\beta}+(N-1-k)^{1-\beta}(N-x)^{\beta}, \quad x\geq \frac{Nk}{N-1}\) is an increasing function on \(x\geq \frac{Nk}{N-1}\) as \(\beta<0\). From equation (3) and Lemma 3.2, we have

\[\frac{Nk}{N-1} \le x \le \frac{Nk + \sqrt{\theta}}{N-1},\]

where \(\theta = k(N - 1 - k)(2(N - 1)R_{-1} - 2)\). Hence

\[S_{\beta}^*(\Gamma(\mathbb{Z}_n)) \le f\left(\frac{Nk + \sqrt{\theta}}{N - 1}\right),\]

and inequality follows. Equality can be easily checked by Lemma 3.2.

Acknowledgements. The research of S. Pirzada is supported by SERB-DST, New Delhi under the research project number MTR/2017/000084.

References

• [1] D.F. Anderson and P.S. Livingston, The zero divisor graph of a commutative ring, J. Algebra 217 (1999) 434–447.
• [2] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988) 208–226.

• [3] S¸. Bozkurt and D. Bozkurt, On the sum of powers of normalized laplacian eigenvalues of graphs, MATCH Commun. Math. Comput. Chem. 68 (2012) 917–930.
• [4] D.M. Cardoso, M.A. De Freitas, E.N. Martins, and M Robbiano, Spectra of graphs obtained by a generalization of the join of graph operations, Discrete Math. 313 (2013) 733–741.
• [5] M. Cavers, The normalized Laplacian matrix and general Randic index of graphs, Thesis, University of Regina 2010.
• [6] S. Chattopadhyay, K.L. Patra, and B.K. Sahoo, Laplacian eigenvalues of the zero divisor graph of the ring Zn, Linear Algebra Appl. 584 (2020) 267–286.
• [7] F.R.K. Chung, Spectral Graph Theory American Mathematical Society, Providence, 1997.
• [8] D.M. Cvetkovic, P. Rowlison, and S. Simi ´ c,´ An Introduction to Theory of Graph spectra Lon. Math. Society Student Text, 75. Cambridge University Press, Inc. UK 2010.
• [9] H. Chen and F. Zhang, Resistance distance and the normalized Laplacian spectrum, Discrete Appl. Math. 155 (2007) 654–661.
• [10] K.C. Das, A.D. Gung ¨ or and s¸. Bozkurt, On the normalized Laplacian eigenvalues of graphs, ¨ Ars Combin. 118 (2015) 143–154.
• [11] R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, 1985.
• [12] S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient BlackSwan, Hyderabad (2012).
• [13] S. Pirzada, B.A. Rather, A. Ahmad, and T.A. Chishti, On distance signless Laplacian spectrum of graphs and spectrum of zero divisor graphs of Zn, Linear Multilinear Algebra, https://doi.org/10.1080/03081087.2020.1838425
• [14] S. Pirzada, B.A. Wani, and A. Somasundaram, On the eigenvalues of zero divisor graph associated to finite commutative ring ZpMq^N , AKCE International J. Graphs Combinatorics, https://doi.org/10.1080/09728600.2021.1873060
• [15] S. Pirzada, B.A. Rather, and T.A. Chishti, On distance Laplacian spectrum of zero divisor graphs of Zn, Carpathian Mathematical Publications 13 (1) (2021), 48–57. https://doi:10.15330/cmp.13.1.48-57
• [16] S. Pirzada, B.A. Rather, R.U. Shaban, and Merajuddin, On signless Laplacian spectrum of the zero divisor graph of the ring Zn, Korean J. Mathematics 29 (1) (2021), 13–24. https://doi.org/10.11568/kjm.2021.29.1.13
• [17] B.A. Rather, S. Pirzada, T.A. Naikoo, and Y. Shang, On Laplacian eigenvalues of the zerodivisor graph associated to the ring of integers modulo n, Mathematics, 9 (5) (2021), 482. https://doi.org/10.3390/math9050482

• [18] B.F. Wu, Y.Y. Lou, and C.X. He, Signless Laplacian and normalized Laplacian on the H-join operation of graphs, Discrete Math. Algorithm. Appl. 6 (2014) (13 pages).
• [19] M. Young, Adjacency matrices of zero divisor graphs of integer modulo n, Involve 8 (2015), 753–761.
• [20] P. Zumstein, Comparison of Spectral Methods Through the Adjacency Matrix and the Laplacian of a Graph, Diplomat thesis, ETH Zurich, 2006. ¨