The normalized Laplacian spectrum of subdivisions of a graph

The normalized Laplacian spectrum of subdivisions of a graph Pinchen Xiea,b, Zhongzhi Zhanga,c, Francesc Comellasd aShanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China bDepartment of Physics, Fudan University, Shanghai 200433, China cSchool of Computer Science, Fudan University, Shanghai 200433, China dDepartment of Applied Mathematics IV, Universitat Polit`ecnica de Catalunya, 08034 Barcelona Catalonia, Spain Abstract Determining and analyzing the spectra of graphs is an important and exciting research topic in mathematics science and theoretical computer science. The eigenvalues of the normalized Laplacian of a graph provide information on its structural properties and also on some relevant dynamical aspects, in particular those related to random walks. In this paper, we give the spectra of the normalized Laplacian of iterated subdivisions of simple connected graphs. As an example of application of these results we find the exact values of their multiplicative degree-Kirchhoff index, Kemeny’s constant and number of spanning trees. Keywords: Normalized Laplacian spectrum, Subdivision graph, Degree-Kirchhoff index, Kemeny’s constant, Spanning trees 1. Introduction Spectral analysis of graphs has been the subject of considerable research effort in mathematics and computer science [1, 2, 3], due to its wide applications in this area and in general [4, 5]. In the last few decades a large body of scientific literature has established that important structural and dynamical properties of networked systems are encoded in the eigenvalues and eigenvectors of some matrices associated to their graph representations. The spectra of the adjacency, Laplacian and normalized Laplacian matrices Email addresses: [email protected] (Zhongzhi Zhang), [email protected] (Francesc Comellas) Preprint submitted to Applied Mathematics and Computation April 27, 2016 of a graph provide information on bounds on the diameter, maximum and minimum degrees, possible partitions, and can be used to count the number of paths of a given length, number of triangles, total number of links, number of spanning trees and many more invariants. Dynamic aspects of a network, like its synchronizability and random walks properties can be determined from the eigenvalues of the Laplacian and normalized Laplacian matrices which allow also the calculation of some interesting graph invariants like the Kirchhoff index [6, 7, 8]. We notice that in the last years there has been an increasing interest in the study of the normalized Laplacian as many measures for random walks on a network are linked to the eigenvalues and eigenvectors of normalized Laplacian of the associated graph, including the hitting time, mixing time and Kemeny’s constant which can be used as a measure of efficiency of navigation on the network, see [9, 10, 11, 12]. However, the normalized and standard Laplacian matrices of a network behave quite differently [13], and even if the spectrum of one matrix can be determined, it does not mean that the other can also be evaluated unless the graph is regular. As an example, the eigenvalues of the Laplacian of Vicsek fractals can be found analytically [14], but until now it has not been possible to obtain the spectra of their normalized Laplacian. Thus, the spectra of the standard and normalized Laplacian matrices must be considered independently. In this paper, we give the spectra of the normalized Laplacian of iterated subdivisions of simple connected graphs and we use these results to find the values of their multiplicative degree-Kirchhoff index, Kemeny’s constant and number of spanning trees. 2. Preliminaries Let G(V, E) be any simple connected graph with vertex set Vand edge set E. Let N0=|V|denote the number of vertices of Gand E0=|E|its number of edges. Definition 2.1 The subdivision graph of G, denoted by s(G), is the graph obtained from Gby inserting an additional vertex to every edge of G. We denote s0(G) = G. The n-th subdivision of Gis obtained through the iteration sn(G) = s(sn−1(G)) and Nnand Endenote the total number of vertices and edges of sn(G). Figure 1 illustrates the iterated subdivisions of four-vertex complete graph K4. 2 Figure 1: K4,s(K4) and s2(K4). Black vertices denote the initial vertices of K4while red and green vertices are those introduced to obtain s(K4) and s2(K4), respectively. From the definition of the subdivision graph, it is obvious that En= 2En−1and Nn=Nn−1+En−1. Thus, for n > 0, we have En= 2nE0, Nn=N0+ (2n−1)E0.(1) Moreover, for any vertex, once it is created, its degree remains unchanged as ngrows. Definition 2.2 The circuit rank or cyclomatic number of Gis the minimum number rof edges that have to be removed from Gto convert the graph into a tree. Obviously, the circuit rank of Gis r=E0−N0+ 1. Lemma 2.3 The circuit rank of sn(G)and Gare the same for n⩾0. Proof. From the definition of the subdivision graph and (1), the circuit rank of sn(G) is r=En−Nn+ 1 = E0−N0+ 1. 2 Given the subdivision graph sn(G) we label its nodes from 1 to Nn. Let dibe the degree of vertex i, then Dn= diag(d1, d2,··· , dNn) denotes the diagonal degree matrix of sn(G) and Anits adjacency matrix, defined as a matrix with the (i, j)-entry equal to 1 if vertices iand jare adjacent and 0 otherwise. We introduce now the probability transition matrix for random walks on sn(G) or Markov matrix as Mn=D−1 nAn.Mncan be normalized to obtain a symmetric matrix Pn. Pn=D−1 2 nAnD−1 2 n=D 1 2 nMnD−1 2 n.(2) The (i, j)th entry of Pnis (Pn)ij =An(i,j) √didj . 3 Definition 2.4 The normalized Laplacian matrix of sn(G)is Ln=I−D 1 2 nMnD−1 2 n=I−Pn,(3) where Iis the identity matrix with the same order as Pn. We denote the spectrum of Lnby σn=nλ(n) 1, λ(n) 2,··· , λ(n) Nno. It is known that 0 = λ(n) 1< λ(n) 2⩽··· ⩽λ(n) Nn−1⩽λ(n) Nn⩽2. The spectrum of the normalized Laplacian matrix of a graph provides us with relevant structural information about the graph, see [7, 15]. Below, we will then relate σnto some significant invariants of sn(G). Definition 2.5 Replacing each edge of a simple connected graph Gby a unit resistor, we obtain an electrical network G∗corresponding to G. The resistance distance rij between vertices iand jof Gis equal to the effective resistance between the two equivalent vertices of G∗[16]. Definition 2.6 The multiplicative degree-Kirchhoff index of Gis defined as [17]: Kf∗(G) = X i<j didjrij.(4) This index is different from the classical Kirchhoff index [18], Kf(G) = Pi<j rij, as it takes into account the degree distribution of the graph. It has been proved [17] that Kf∗(G) can be obtained from the spectrum σ0={λ1, λ2,··· , λN0}of the normalized Laplacian matrix L0of G: Kf∗(G)=2E0 N0 X k=2 1 λk ,(5) where 0 = λ1< λ2⩽··· ⩽λN0⩽2. Thus, for n⩾0, we have: Kf∗(sn(G)) = 2En Nn X k=2 1 λ(n) k ,(6) where 0 = λ(n) 1< λ(n) 2⩽··· ⩽λ(n) Nn−1⩽λ(n) Nn⩽2 are the eigenvalues of Ln. Definition 2.7 Given a graph G, the Kemeny’s constant K(G), also known as average hitting time, is the expected number of steps required for the transition from a starting vertex ito a destination vertex, which is chosen randomly according to a stationary distribution of unbiased random walks on G, see [19] for more details. 4 It is known that K(G) is a constant as it is independent of the selection of starting vertex i, see [12]. Moreover, the Kemeny’s constant can be computed from the normalized Laplacian spectrum in a very simple way as the sum of all reciprocal eigenvalues, except 1/λ1, see [15]. Thus, we can write, for sn(G) and σn: K(sn(G)) = Nn X k=2 1 λ(n) k .(7) The last graph invariant considered in this paper is the number of spanning trees of a graph G. A spanning tree is a subgraph of Gthat includes all the vertices of Gand is a tree. A known result from Chung [7] allows the calculation of this number from the normalized Laplacian spectrum and the degrees of all the vertices, thus the number of spanning trees N(n) st of sn(G) is N(n) st = Nn Y i=1 di Nn Y i=2 λ(n) i Nn X i=1 di .(8) In the next section we provide an analytical expression for this invariant for any value of n⩾0. 3. Normalized Laplacian spectrum of the subdivision graph sn(G) In this section we find an analytical expression for the spectrum σnof Ln(sn(G)), the normalized Laplacian of the subdivision graph sn(G). We show that this spectrum can be obtained iteratively from the spectrum of G. As Ln=I−Pn, if µis an eigenvalue of Pnthen 1 −µis an eigenvalue of Lnwith the same multiplicity. We denote the multiplicity of µas mPn(µ). Thus we calculate first the spectrum σ0 nof Pn. Lemma 3.1 Let µbe any nonzero eigenvalue of Pnand let R(x)=2x2−1. Then, R(µ)is an eigenvalue of Pn−1with the same multiplicity as µ. Proof. Divide the vertices of sn(G) into two groups Vn old and Vn new, where Vn new contains all the vertices created when the edges of sn−1(G) are subdivided to generate sn(G) and Vn old contains the rest. Obviously, Vn old has the same vertices as sn−1(G). Thus for convenience, in the following when any vertex of Vn old is considered, it also refers to the corresponding vertex of sn−1(G). 5 Let ψ= (ψ1, ψ2, . . . , ψNn)>be any eigenvector associated to an eigenvalue µof Pn. Hence Pnψ=µψ (9) Consider a vertex i∈Vn old of sn(G) and denote Nthe set of all its neighbors in sn(G) and N0the set of all its neighbors in sn−1(G). From the definition of subdivision graph, there exists a bijection between Nand N0. If we rewrite Eq. (9) as PNn j=1(Pn)ijψj=µψi,we have µψi=X j∈N 1 pdidj ψj=X j∈N 1 √2di ψj.(10) For any vertex j∈ N, we have a similar relation µψj= Nn X k=1 (Pn)jkψk=1 √2di ψi+1 p2dj0 ψj0.(11) where vertex j0∈ N0is the other neighbor of vertex jin sn(G) . Combining Eq. (10) and Eq. (11) yields µψi=1 µ√2di×X j0∈N 0 1 √2di ψi+1 p2dj0 ψj0! =1 µ√2di× di √2di ψi+X j0∈N 0 1 p2dj0 ψj0 . (12) Therefore, (2µ2−1)ψi=X j0∈N 0 1 pdidj0 ψj0.(13) Eq. (13) directly reflects that R(µ) = (2µ2−1) is an eigenvalue of Pn−1, ψo= (ψi)> i∈Vn old is one of its corresponding eigenvectors and ψcan be totally determined by ψoby using Eq. (11). Hence mPn−1(R(µ)) ⩾mPn(µ). Suppose now that mPn−1(R(µ)) > mPn(µ). Then there exists an extra eigenvector ψeassociated to R(µ) without an associated eigenvector in Pn. But Eq. (11) provides ψewith its corresponding eigenvector in Pnas µis nonzero, in contradiction with our assumption. Thus mPn−1(R(µ)) = mPn(µ) and the proof is completed. 2 6 Lemma 3.2 Let µbe any eigenvalue of Pn−1such that µ6=−1and let f1(x) = qx+1 2and f2(x) = −qx+1 2. Then f1(µ)and f2(µ)are eigenvalues of Pn. Besides, mPn(f1(µ)) = mPn(f2(µ)) = mPn−1(µ). Proof. This lemma is a direct consequence of Lemma 3.1 2 Remark 3.3 Lemmas 3.1 and 3.2 indicate that any nonzero eigenvalues of Pncan be obtained from the spectrum of Pn−1. Due to the simple expression of R,f1and f2, we easily find that each eigenvalue, except −1, of Pn−1 will generate two unique eigenvalues of Pn. Thus 2(Nn−1−mPn−1(−1)) eigenvalues of σ0 n, and consequently of σn, are determined this way. The Perron-Frobenius theorem [20] shows that the largest absolute value of the eigenvalues of Pnis always 1. And because of the existence of a unique stationary distribution for random walks on sn(G), the multiplicity of the eigenvalue 1 is always 1 for any n⩾0. Since f2(1) = −1, we also obtain mPn(−1) = 1 for any n⩾1. This can be further explained from the perspective of Markov chains. Since sn(G) is a bipartite graph [21] containing no odd-length cycles for any n > 0, random walks on it are periodic with period 2, which means it takes an even number of steps to return to the starting vertex. Thus the smallest eigenvalue of the Markov matrix of sn(G) is −1 [22]. But random walks on a general graph Gcan be aperiodic [23] if the graph has an odd-length cycle. Hence the multiplicity of the eigenvalue −1 of P0depends on the structure of G[22]. Lemmas 3.1 and 3.2 allow us to obtain the transition between the eigenvalues of the normalized Laplacian of sn(G) at each iteration step. If µis an eigenvalue of Pnthen λ= 1−µis an eigenvalue of Ln. Let Q(x) = 4x−2x2, by Lemma 3.1, Q(λ)=1−R(1 −λ) is an eigenvalue of Ln−1if λ6= 1. This allows us to state the following lemma: Lemma 3.4 Let λbe any eigenvalue of Ln−1such that λ6= 2 and let g1(x) = 1 + p1−x 2and g2(x)=1−p1−x 2. Then g1(λ)and g2(λ) are eigenvalues of Lnand mLn(g1(λ)) = mLn(g2(λ)) = mLn−1(λ). 2 Definition 3.5 Let U={u1, u2,··· , uk}be any finite multiset of real numbers where |ui|⩽1for i∈[1, k]. The multisets R−1(U)and Q−1(U)are defined as R−1(U) = {f1(u1), f2(u1), f1(u2), f2(u2),··· , f1(uk), f2(uk)}; (14) 7 Q−1(U) = {g1(u1), g2(u1), g1(u2), g2(u2),··· , g1(uk), g2(uk)}.(15) Our main result in this section is the following theorem. Lemma 3.6 The spectrum σ0 nof Pn, for n > 0, is: σ0 n=R−1σ0 n−1\{−1}∪{0,··· ,0 | {z } mPn(0) }(16) When n > 1,mPn(0) = r+ 1. When n= 1, if G contains any odd-length cycle then mPn(0) = r−1, otherwise mPn(0) = r+ 1, where ris the circuit rank of G. Proof. Combining Lemma 3.1, Lemma 3.2 and considering Remark 3.3, the multiplicity of the eigenvalue 0 of Pncan be determined indirectly: mPn(0) = Nn−2(Nn−1−mPn−1(−1)) =E0−N0+ 2 ·mPn−1(−1).(17) Based on the previous results, it is obvious that mPn−1(−1) = 0 if and only if n= 1 and G contains an odd-length cycle, otherwise mPn−1(−1) = 1, which completes the proof. 2 This result allows us to state the main result of this section. Theorem 3.7 The spectra σnof Lnis obtained from σn−1of Ln−1as: σn=Q−1(σn−1\{2})∪{1,··· ,1 | {z } mLn(1) }(18) for n > 0and where mLn(1) = mPn(0) is the multiplicity of the eigenvalue 1of Ln. 2 Due to the particularity of the eigenvalue 1 of Ln, we call it the exceptional eigenvalue [24] of the family of matrices {Ln}whose spectra show self-similar characteristics. For many other family of graphs [24, 25] with a similar self-similar property with respect to the spectra of their Markov matrices, the multiplicity of exceptional eigenvalues grows fast as nincreases. However, for the normalized Laplacian of subdivision graphs {sn(G)}, the multiplicity of the only exceptional eigenvalue 1 is always r+ 1 for n > 1. 8 4. Application of the spectrum of subdivision graph In this section we use the spectra of Ln, the normalized Laplacian of the subdivision graph sn(G), to compute some relevant invariants related to the structure of sn(G). Thus, we give closed formulas for the multiplicative degree-Kirchhoff index, Kemeny’s constant and the number of spanning trees of sn(G). These results depend only on nand some invariants of the original graph G. 4.1. Multiplicative degree-Kirchhoff index Theorem 4.1 The multiplicative degree-Kirchhoff indices of sn(G)and sn−1(G) are related as follows, for any n > 0: Kf∗(sn(G)) = 8Kf∗(sn−1(G)) + 2n(2r−1)E0.(19) Therefore, the general expression for Kf∗(sn(G)) is Kf∗(sn(G)) = 8nKf∗(G) + 8n−2n 3(2r−1)E0.(20) Proof. From Eq. (6) and Corollary 3.7, the relation between Kf∗(sn(G)) and Kf∗(sn−1(G)) can be expressed as: Kf∗(sn(G)) = 2En  1 λ(n) Nn +mLn(0) 1−0+ Nn−1−1 X k=2 1 g1(λ(n−1) k)+1 g2(λ(n−1) k)!  = 2En  1 2+ (r+ 1) + 4 Nn−1−1 X k=2 1 λ(n−1) k  = 2En1 2+ (r+ 1) + 4 K(sn−1(G)) 2En−1 − 1 2 = 8Kf∗(sn−1(G)) + 2n(2r−1)E0, (21) provided that mLn−1(−1) = 1, where λ(n) krepresents the eigenvalue of Ln. When n= 1 and mLn0(−1) = 0, we obtain: Kf∗(s(G)) = 2E1 1 λN1 +mL1(0) 1−0+ N0 X k=2 1 g1(λk)+1 g2(λk)! = 2E1 1 2+ (r−1) + 4 N0 X k=2 1 λk! = 2E11 2+ (r−1) + 4 · K(G) 2E0 = 8Kf∗(G) + 2(2r−1)E0. (22) 9