# Generalized Characteristic Polynomials of Join Graphs and Their Applications

Authors: Pengli Lu; Ke Gao; Yang Yang
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

The Kirchhoff index ofG is the sum of resistance distances between all pairs of vertices of G in electrical networks. LEL(G) is the Laplacian-Energy-Like Invariant of G in chemistry. In this paper, we define two classes of join graphs: the subdivision-vertex-vertex join G1⊚G2 and the subdivision-edge-edge join G1⊝G2. We determine the generalized characteristic polynomial of them. We deduce the adjacency (Laplacian and signless Laplacian, resp.) characteristic polynomials of G1⊚G2 and G1⊝G2 when G1 is r1-regular graph and G2 is r2-regular graph. As applications, the Laplacian spectra enable us to get the formulas of the number of spanning trees, Kirchhoff index, and LEL of G1⊚G2 and G1⊝G2 in terms of the Laplacian spectra of G1 and G2.


---

## Body

## 1. Introduction

LetG=(V(G),E(G)) be a simple graph on n vertices and m edges. Let di=dG(vi) be the degree of vertex vi in G and D(G) be thediagonal matrix with diagonal entries d1,d2,…,dn. Let A(G) denote theadjacency matrix of a graph G. TheLaplacian matrix and thesignless Laplacian matrix of G are defined as L(G)=D(G)-A(G) and Q(G)=D(G)+A(G), respectively. Let ψ(A(G);x)=det⁡(xIn-A(G)), or simply ψ(A(G)) (ψ(L(G)) and ψ(Q(G)), resp.), be theadjacency (Laplacian andsignless Laplacian, resp.)characteristic polynomial of G and its roots be theadjacency (Laplacian andsignless Laplacian, resp.)eigenvalues of G, denoted by λ1(G)≥λ2(G)≥⋯≥λn(G) (0=μ1(G)≤μ2(G)≤⋯≤μn(G) and ν1(G)≤ν2(G)≤⋯≤νn(G), resp.). The line graph of G is denoted by l(G).Thegeneralized characteristic polynomial of G, introduced by Cvetkovi et al. [1], is defined to be ϕG(x,t)=det⁡(xIn-(A(G)-tD(G))). The generalized characteristic polynomial covers the cases of usual characteristic polynomial A(G) and Laplacian L(G) and signless Laplacian Q(G) polynomials of graph G, due to variation of the parameter t and, whenever necessary, replacing x by -x. We can get that the characteristic polynomials of A(G), L(G), and Q(G) are equal to ϕG(x,0), (-1)|V(G)|ϕG(-x,1), and ϕG(x,-1).LetG be a connected graph. For two vertices u and v of G, theresistance distance between u and v is defined to be the effective resistance between them when unit resistors are placed on every edge of G. It is a distance function on graphs introduced by Klein and Randić [2]. TheKirchhoff index of G, denoted by Kf(G), is the sum of resistance distances between all pairs of vertices of G. For a connected graph G of order n [3], Kf(G)=n∑i=2n1/μi. Recently, many results on Kirchhoff index were obtained [2, 4–8].Laplacian-Energy-Like InvariantLEL(G)=∑i=2nμi was named in [9]. The motivation for introducing LEL was in its analogy to the earlier studied graph energy and Laplacian energy [10]. Although Kirchhoff index and LEL both depend on Laplacian eigenvalues, their comparative study started only quite recently [11, 12].Graph operations, such as thedisjoint union, thejoin, thecorona, theedge corona, and theneighborhood corona [13–17], are techniques to construct new classes of graphs from old ones. In [18], a real molecular graph of ferrocene is a join graph obtained from graphs G1=K1 and G2=2C5, where 2C5 is a disjoint union of two pentagons. In [4–6, 8, 14] the resistance distance and Kirchhoff index of artificial graphs are computed. Although most of the constructed graphs in the literature are contrived, they may be of use for chemical and physical applications.Motivated by the work above, we define two new graph operations based onsubdivision graphs as follows.The subdivision graphS(G) of a graph G is the graph obtained by inserting a new vertex into every edge of G [19]. We denote the set of such new vertices by I(G). In [15, 20], some new graph operations based on subdivision graphs were defined and the A-, L-, and Q-spectrum were computed in terms of those of the two graphs.LetG1 and G2 be two vertex disjoint graphs. The subdivision-vertex-vertex join of G1 and G2, denoted by G1⊚G2, is the graph obtained from S(G1) and S(G2) by joining every vertex in V(G1) to every vertex in V(G2). The subdivision-edge-edge join of G1 and G2, denoted by G1⊝G2, is the graph obtained from S(G1) and S(G2) by joining every vertex of I(G1) to every vertex in I(G2).Note that ifG1 is a graph on n1 vertices and m1 edges and G2 is a graph on n2 vertices and m2 edges, then G1⊚G2 has n1+m1+n2+m2 vertices and 2m1+2m2+n1n2 edges and G1⊝G2 has n1+m1+n2+m2 vertices and 2m1+2m2+m1m2 edges.LetCn denote a cycle of order n and Pm denote a path of order m. Figure 1 depicts thesubdivision-vertex-vertex joinC5⊚P2 andsubdivision-edge-edge joinC5⊝P2, respectively.Figure 1
An example ofsubdivision-vertex-vertex join andsubdivision-edge-edge join.The paper is organized as follows. In Section2, some useful lemmas are provided. In Section 3, we compute the generalized characteristic polynomial of the subdivision-vertex-vertex join and obtain the A-, L-, and Q-spectrum in terms of the corresponding spectrum of G1 and G2 when G1 and G2 are regular graphs. In Section 4, we compute the generalized characteristic polynomial of the subdivision-edge-edge join and obtain the A-, L-, and Q-spectrum in terms of the corresponding spectrum of G1 and G2 when G1 and G2 are regular graphs. In Section 5, as the applications, the number of spanning trees, Kirchhoff index, and LEL of the subdivision-vertex-vertex join and the subdivision-edge-edge join graphs are computed. In Section 6, we conclude the paper.


## 2. Preliminaries

TheM-coronal ΓM(x) of an n×n matrix M is defined [16] to be the sum of entries of the matrix (xIn-M)-1; that is (1)ΓMx=1nTxIn-M-11n,where 1n denotes the column vector of size n when all the entries are equal to one.Lemma 1 (see [21]).
LetA be an n×n real matrix and let Js×t denote the s×t matrix with all entries equal to one. Then (2)det⁡A+αJn×n=det⁡A+α1nTadjA1n,where α is a real number and adj(A) is the adjugate matrix of A. Moreover, (3)det⁡xIn-A-αJn×n=1-αΓAxdet⁡xIn-A.Lemma 2 (see [13]).
IfM is an n×n matrix when each row sum is equal to a constant t; then, (4)ΓMx=nx-t.Lemma 3 (see [22]).
LetM1, M2, M3, and M4 be, respectively, p×p, p×q, q×p, and q×q matrices with M1 and M4 invertible. Then (5)det⁡M1M2M3M4=det⁡M4·det⁡M1-M2M4-1M3=det⁡M1·det⁡M4-M3M1-1M2,where M1-M2M4-1M3 and M4-M3M1-1M2 are called the Schur complements of M4 and M1, respectively.Lemma 4 (see [19]).
IfG is a regular graph of degree r, with n vertices and m edges; then (6)ψAlG,x=x+2m-nψAG,x-r+2.IfA=[aij] is an m×n matrix and B is an r×s matrix, then the Kronecker product A⊗B is defined as the mr×ns matrix with the block form(7)a11B…a1nB⋮⋱⋮am1B…amnB.This is an associative operation with the property thatA⊗BT=AT⊗BT and A⊗BC⊗D=AC⊗BD whenever the products AC and BD exist. The latter implies A⊗B-1=A-1⊗B-1 for nonsingular matrices A and B. Moreover, if A and B are n×n and p×p matrices, then det⁡(A⊗B)=det⁡Apdet⁡Bn. The reader is referred to [23] for other properties of the Kronecker product not mentioned here.


## 3. Spectrum of Subdivision-Vertex-Vertex Join

LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges, respectively. We first label the vertices of G1⊚G2 as follows. Let V(G1)=v1,v2,…,vn1, IG1=e1,e2,…,em1, V(G2)=u1,u2,…,un2, and I(G2)=e1,e2,…,em2. The adjacency matrix of G1⊚G2 can be written as follows: (8)AG1⊚G2=0m1×m1R1T0m1×n20m1×m2R10n1×n11n1×n20n1×m20n2×m11n2×n10n2×n2R20m2×m10m2×n1R2T0m2×m2,where 0s×t denotes the s×t matrix with all entries equal to zero, R is the incidence matrix of G, In is the identity matrix of order n, and 1n is the column vector with all entries equal to 1. It is clear that the degrees of the vertices of G1⊚G2 are dG1⊚G2(vi)=r1+n2 for i=1,2,…,n1, dG1⊙G2(ei)=2 for i=1,2,…,m1, dG1⊚G2(ui)=r2+n1 for i=1,2,…,n2, and dG1⊚G2(ei)=2 for i=1,2,…,m2. Then the degree matrix of subdivision-vertex-vertex join can be written as follows:(9)DG1⊚G2=2Im10m1×n10m1×n20m1×m20n1×m1r1+n2In10n1×n20n1×m20n2×m10n2×n1r2+n1In20n2×m20m2×m10m2×n10m2×n22Im2.


### 3.1. Generalized Characteristic Polynomial ofG1⊚G2

Theorem 5.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 be an r2-regular graph on n2 vertices and m2 edges. Then the generalized characteristic polynomial of subdivision-vertex-vertex join of G1 and G2 is (10)ϕG1⊚G2x,t=x+2tm1+m2-n1-n2∏i=1n1x2+2t+r1t+n2tx+2r1t2+2n2t2-λiG1-r1·∏i=1n2x2+2t+r2t+n1tx+2r2t2+2n1t2-λiG2-r2·1-n1n2x+2t2x+r1t+n2tx+2t-2r1x+r2t+n1tx+2t-2r2.Proof.
LetR1 be the incidence matrix of G1. Then, with respect to the adjacent matrix and degree matrix of G1⊚G2, the generalized matrix of G1⊚G2 is given by(11)AG1⊚G2-tDG1⊚G2=-2tIm1R1T0m1×n20m1×m2R1-r1+n2tIn11n1×n20n1×m20n2×m11n2×n1-r2+n1tIn2R20m2×m10m2×n1R2T-2tIm2.Thus the generalized characteristic polynomial of G1⊚G2 is(12)ϕG1⊚G2x,t=det⁡x+2tIm1-R1T0m1×n20m1×m2-R1x+r1t+n2tIn1-1n1×n20n1×m20n2×m1-1n2×n1x+r2t+n1tIn2-R20m2×m10m2×n1-R2Tx+2tIm2=det⁡x+2tIm1det⁡S=x+2tm1det⁡S,where(13)S=x+r1t+n2tIn1-1n1×n20n1×m2-1n2×n1x+r2t+n1tIn2-R20m2×n1-R2Tx+2tIm2--R10n2×n10m2×n1·x+2tIm1-1-R1T0m1×n10m1×m2=x+r1t+n2tIn1-R1R1Tx+2t-1n1×n20n1×m2-1n2×n1x+r2t+n1tIn2-R20m2×n1-R2Tx+2tIm2is the Schur complement of (x+2t)Im1. So, det⁡(S)=x+2tm2det⁡(S1), where(14)S1=x+r1t+n2tIn1-R1R1Tx+2t-1n1×n2-1n2×n1x+r2t+n1tIn2-0n1×m2-R2x+2tIm2-10m2×n1-R2T=x+r1t+n2tIn1-R1R1Tx+2t-1n1×n2-1n2×n1x+r2t+n1tIn2-R2R2Tx+2tis the Schur complement of x+2tIm2. So, (15)det⁡S1=det⁡x+r1t+n2tIn1-R1R1Tx+2t·det⁡x+r2t+n1tIn2-R2R2Tx+2t-1n2×n1x+r1t+n2tIn1-R1R1Tx+2t-11n1×n2is the Schur complement of (x+r1t+n2t)In1-R1R1T/x+2t. So,(16)ϕG1⊚G2x,t=x+2tm1+m2det⁡x+r1t+n2tIn1-R1R1Tx+2t·det⁡x+r2t+n1tIn2-R2R2Tx+2t-1n2×n1x+r1t+n2tIn1-R1R1Tx+2t-11n1×n2=x+2tm1+m2det⁡x+r1t+n2tIn1-AG1+DG1x+2t·det⁡x+r2t+n1tIn2-R2R2Tx+2t-1n2×n1x+r1t+n2tIn1-R1R1Tx+2t-11n1×n2=x+2tm1+m2∏i=1n1x+r1t+n2t-λiG1+r1x+2t·det⁡x+r2t+n1tIn2-R2R2Tx+2t-ΓR1R1T/x+2tx+r1t+n2t1n2×n2;by Lemma 1,(17)ϕG1⊚G2x,t=x+2tm1+m2∏i=1n1x+r1t+n2t-λiG1+r1x+2t·1-ΓR1R1T/x+2tx+r1t+n2tΓR2R2T/x+2tx+r2t+n1tdet⁡x+r2t+n1tIn2-R2R2Tx+2t=∏i=1n1x2+2t+r1t+n2tx+2r1t2+2n2t2-λiG1-r1·∏i=1n2x2+2t+r2t+n1tx+2r2t2+2n1t2-λiG2-r2·1-ΓR1R1T/x+2tx+r1t+n2tΓR2R2T/x+2tx+r2t+n1tx+2tm1+m2-n1-n2=x+2tm1+m2-n1-n2∏i=1n1x2+2t+r1t+n2tx+2r1t2+2n2t2-λiG1-r1·∏i=1n2x2+2t+r2t+n1tx+2r2t2+2n1t2-λiG2-r2·1-n1n2x+2t2x+r1t+n2tx+2t-2r1x+r2t+n1tx+2t-2r2.Theorem 6.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges. Then(1)
the adjacency characteristic polynomial ofG1⊚G2 is (18)ψAG1⊚G2;x=xm1+m2-n1-n2∏i=1n1x2-r1-λiG1∏i=1n2x2-r2-λiG2·1-n1n2x2x4-2r1+r2x2+4r1r2,(2)
the Laplacian characteristic polynomial ofG1⊚G2 is (19)ψLG1⊚G2;x=∏i=2n1x2-r1+n2+2x+2n2+μiG1∏i=2n2x2-r2+n1+2x+2n1+μiG2·xx3-n1+n2+r1+r2+4x2+4n1+4n2+2r1+2r2+4+r1r2+r1n1+r2n2x-4n1-4n2-2n1r1-2n2r2x-2m1+m2-n1-n2,(3)
the signless Laplacian characteristic polynomial ofG1⊚G2 is (20)ψQG1⊚G2;x=x-2m1+m2-n1-n2∏i=1n1x2-r1+n2+2x+2n2+2r1-νiG1·1-n1n2x-22x2-2+r1+n2x+2n2x2-2+r2+n1x+2n1·∏i=1n2x2-r2+n1+2x+2n1+2r2-νiG2.


## 3.1. Generalized Characteristic Polynomial ofG1⊚G2

Theorem 5.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 be an r2-regular graph on n2 vertices and m2 edges. Then the generalized characteristic polynomial of subdivision-vertex-vertex join of G1 and G2 is (10)ϕG1⊚G2x,t=x+2tm1+m2-n1-n2∏i=1n1x2+2t+r1t+n2tx+2r1t2+2n2t2-λiG1-r1·∏i=1n2x2+2t+r2t+n1tx+2r2t2+2n1t2-λiG2-r2·1-n1n2x+2t2x+r1t+n2tx+2t-2r1x+r2t+n1tx+2t-2r2.Proof.
LetR1 be the incidence matrix of G1. Then, with respect to the adjacent matrix and degree matrix of G1⊚G2, the generalized matrix of G1⊚G2 is given by(11)AG1⊚G2-tDG1⊚G2=-2tIm1R1T0m1×n20m1×m2R1-r1+n2tIn11n1×n20n1×m20n2×m11n2×n1-r2+n1tIn2R20m2×m10m2×n1R2T-2tIm2.Thus the generalized characteristic polynomial of G1⊚G2 is(12)ϕG1⊚G2x,t=det⁡x+2tIm1-R1T0m1×n20m1×m2-R1x+r1t+n2tIn1-1n1×n20n1×m20n2×m1-1n2×n1x+r2t+n1tIn2-R20m2×m10m2×n1-R2Tx+2tIm2=det⁡x+2tIm1det⁡S=x+2tm1det⁡S,where(13)S=x+r1t+n2tIn1-1n1×n20n1×m2-1n2×n1x+r2t+n1tIn2-R20m2×n1-R2Tx+2tIm2--R10n2×n10m2×n1·x+2tIm1-1-R1T0m1×n10m1×m2=x+r1t+n2tIn1-R1R1Tx+2t-1n1×n20n1×m2-1n2×n1x+r2t+n1tIn2-R20m2×n1-R2Tx+2tIm2is the Schur complement of (x+2t)Im1. So, det⁡(S)=x+2tm2det⁡(S1), where(14)S1=x+r1t+n2tIn1-R1R1Tx+2t-1n1×n2-1n2×n1x+r2t+n1tIn2-0n1×m2-R2x+2tIm2-10m2×n1-R2T=x+r1t+n2tIn1-R1R1Tx+2t-1n1×n2-1n2×n1x+r2t+n1tIn2-R2R2Tx+2tis the Schur complement of x+2tIm2. So, (15)det⁡S1=det⁡x+r1t+n2tIn1-R1R1Tx+2t·det⁡x+r2t+n1tIn2-R2R2Tx+2t-1n2×n1x+r1t+n2tIn1-R1R1Tx+2t-11n1×n2is the Schur complement of (x+r1t+n2t)In1-R1R1T/x+2t. So,(16)ϕG1⊚G2x,t=x+2tm1+m2det⁡x+r1t+n2tIn1-R1R1Tx+2t·det⁡x+r2t+n1tIn2-R2R2Tx+2t-1n2×n1x+r1t+n2tIn1-R1R1Tx+2t-11n1×n2=x+2tm1+m2det⁡x+r1t+n2tIn1-AG1+DG1x+2t·det⁡x+r2t+n1tIn2-R2R2Tx+2t-1n2×n1x+r1t+n2tIn1-R1R1Tx+2t-11n1×n2=x+2tm1+m2∏i=1n1x+r1t+n2t-λiG1+r1x+2t·det⁡x+r2t+n1tIn2-R2R2Tx+2t-ΓR1R1T/x+2tx+r1t+n2t1n2×n2;by Lemma 1,(17)ϕG1⊚G2x,t=x+2tm1+m2∏i=1n1x+r1t+n2t-λiG1+r1x+2t·1-ΓR1R1T/x+2tx+r1t+n2tΓR2R2T/x+2tx+r2t+n1tdet⁡x+r2t+n1tIn2-R2R2Tx+2t=∏i=1n1x2+2t+r1t+n2tx+2r1t2+2n2t2-λiG1-r1·∏i=1n2x2+2t+r2t+n1tx+2r2t2+2n1t2-λiG2-r2·1-ΓR1R1T/x+2tx+r1t+n2tΓR2R2T/x+2tx+r2t+n1tx+2tm1+m2-n1-n2=x+2tm1+m2-n1-n2∏i=1n1x2+2t+r1t+n2tx+2r1t2+2n2t2-λiG1-r1·∏i=1n2x2+2t+r2t+n1tx+2r2t2+2n1t2-λiG2-r2·1-n1n2x+2t2x+r1t+n2tx+2t-2r1x+r2t+n1tx+2t-2r2.Theorem 6.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges. Then(1)
the adjacency characteristic polynomial ofG1⊚G2 is (18)ψAG1⊚G2;x=xm1+m2-n1-n2∏i=1n1x2-r1-λiG1∏i=1n2x2-r2-λiG2·1-n1n2x2x4-2r1+r2x2+4r1r2,(2)
the Laplacian characteristic polynomial ofG1⊚G2 is (19)ψLG1⊚G2;x=∏i=2n1x2-r1+n2+2x+2n2+μiG1∏i=2n2x2-r2+n1+2x+2n1+μiG2·xx3-n1+n2+r1+r2+4x2+4n1+4n2+2r1+2r2+4+r1r2+r1n1+r2n2x-4n1-4n2-2n1r1-2n2r2x-2m1+m2-n1-n2,(3)
the signless Laplacian characteristic polynomial ofG1⊚G2 is (20)ψQG1⊚G2;x=x-2m1+m2-n1-n2∏i=1n1x2-r1+n2+2x+2n2+2r1-νiG1·1-n1n2x-22x2-2+r1+n2x+2n2x2-2+r2+n1x+2n1·∏i=1n2x2-r2+n1+2x+2n1+2r2-νiG2.


## 4. Spectrum of Subdivision-Edge-Edge Join

The adjacency matrix ofG1⊝G2 can be written as follows: (21)AG1⊝G2=0n1×n1R10n1×m20n1×n2R1T0m1×m11m1×m20m1×n20m2×n11m2×m10m2×m2R2T0n2×n10n2×m1R20n2×n2,where 0s×t denotes the s×t matrix with all entries equal to zero, R is the incidence matrix of G, In is the identity matrix of order n, and 1n is the column vector with all entries equal to 1. It is clear that the degrees of the vertices of G1⊝G2 are dG1⊝G2(vi)=r1 for i=1,2,…,n1, dG1⊝G2(ei)=m2+2 for i=1,2,…,m1, dG1⊝G2(ui)=r2 for i=1,2,…,n2, and dG1⊝G2(ei)=m1+2 for i=1,2,…,m2. Then the degree matrix of subdivision-edge-edge join can be written as follows:(22)DG1⊝G2=r1In10n1×m10n1×m10n1×n20m1×n1m2+2Im10m1×m20m1×n20m2×n10m2×m1m1+2Im20m2×n20n2×n10n2×m10n2×m2r2In2.


### 4.1. Generalized Characteristic Polynomial ofG1⊝G2

Theorem 7.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 be an r2-regular graph on n2 vertices and m2 edges. Then the generalized characteristic polynomial of subdivision-edge-edge join of G1 and G2 is (23)ϕG1⊝G2x;t=∏i=1n1x2+m2t+2t+r1tx+r1m2t2+2r1t2-λiG1-r1·∏i=1n2x2+m1t+2t+r2tx+r2m1t2+2r2t2-λiG2-r2·1-m1m2x+r1tx+r2tx2+m1t+r2t+2tx+r2m1t2+2r2t2-2r2-1x2+m2t+r1t+2tx+r1m2t2+2r1t2-2r1·x+m1t+2tm2-n2x+m2t+2tm1-n1.Proof.
LetR1 be the incidence matrix of G1. Then, with respect to the adjacent matrix and degree matrix of G1⊝G2, the generalized matrix of G1⊝G2 is given by (24)AG1⊝G2-tDG1⊝G2=-r1tIn1R10n1×m20n1×n2R1T-m2+2tIm11m1×m20m1×n20m2×n11m2×m1-m1+2tIm2R2T0n2×n10n2×m1R2-r2tIn2.Thus the generalized characteristic polynomial of G1⊝G2 is (25)ϕG1⊝G2x;t=det⁡x+r1tIn1-R10n1×m20n1×n2-R1Tx+m2t+2tIm1-1m1×m20m1×n20m2×m1-1m2×m1x+m1t+2tIm2-R2T0n2×n10n2×m1-R2x+r2tIn2=det⁡x+r1tIn1det⁡S=x+r1tn1det⁡S,where(26)S=x+m2t+2tIm1-R1TR1x+r1t-1m1×m20m1×n2-1m2×m1x+m1t+2tIm2-R2T0n2×m1-R2x+r2tIn2is the Schur complement of x+r1tIn1. So, det⁡(S)=x+r2tn2det⁡(S1), where (27)S1=x+m2t+2tIm1-R1TR1x+r1t-1m1×m2-1m2×m1x+m1t+2tIm2-R2TR2x+r2tis the Schur complement of x+r2tIn2. So, (28)det⁡S1=det⁡x+m2t+2tIm1-R1TR1x+r1t·det⁡x+m1t+2tIm2-R2TR2x+r2t-1m2×m1x+m2t+2tIm1-R1TR1x+r1t-11m1×m2is the Schur complement of (x+m2t+2t)Im1-R1TR1/x+r1t. So,(29)ϕG1⊝G2x;t=x+r1tn1x+r2tn2det⁡x+m2t+2tIm1-AlG1+2Im1x+r1t·det⁡x+m1t+2tIm2-R2TR2x+r2t-1m2×m1x+m2t+2tIm1-R1TR1x+r1t-11m1×m2;by Lemma 4,(30)ϕG1⊝G2x;t=x+r1tn1x+r2tn2x+m2t+2tm1-n1∏i=1n1x+m2t+2t-λiG1+r1-2+2x+r1t·det⁡x+m1t+2tIm2-R2TR2x+r2t-ΓR1TR1/x+r1tx+m2t+2t1m2×m2and by Lemma 1,(31)ϕG1⊝G2x;t=x+r1tn1x+r2tn2x+m2t+2tm1-n1∏i=1n1x+m2t+2t-λiG1+r1x+r1t·1-ΓR1TR1/x+r1tx+m2t+2tΓR2TR2/x+r2tx+m1t+2tdet⁡x+m1t+2tIm2-R2TR2x+r2t=∏i=1n1x2+m2t+2t+r1tx+r1m2t2+2r1t2-λiG1-r1·∏i=1n2x2+m1t+2t+r2tx+r2m1t2+2r2t2-λiG2-r2·1-m1m2x+r1tx+r2tx2+m1t+r2t+2tx+r2m1t2+2r2t2-2r2-1x2+m2t+r1t+2tx+r1m2t2+2r1t2-2r1·x+m1t+2tm2-n2x+m2t+2tm1-n1.Theorem 8.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges. Then(1)
the adjacency characteristic polynomial ofG1⊝G2 is (32)ψAG1⊝G2;x=xm1+m2-n1-n2∏i=1n1x2-λiG1-r1∏i=1n2x2-λiG2-r2·1-m1m2x2x4-2r1+r2x2+4r1r2,(2)
the Laplacian characteristic polynomial ofG1⊝G2 is (33)ψLG1⊝G2;x=∏i=2n1x2-m2+2+r1x+r1m2+uiG1∏i=2n2x2-m1+2+r2x+r2m1+uiG2·x-m1-2m2-n2x-m2-2m1-n1·xx3-m1+m2+r1+r2+4x2+r1m2+r2m1+r2m2+r1m1+r1r2+2m1+2m2+2r1+2r2+4x-m1r1r2-m2r1r2-2m1r2-2m2r1,(3)
the signless Laplacian characteristic polynomial ofG1⊝G2 is (34)ψQG1⊝G2;x=∏i=1n1x2-m2+2+r1x+r1m2+2-νiG1x-m2-2m1-n1·1-m1m2x-r1x-r2x2-m2+r1+2x+m2r1x2-m1+r2+2x+m1r2·∏i=1n2x2-m1+2+r2x+r2m1+2-νiG2x-m1-2m2-n2.


## 4.1. Generalized Characteristic Polynomial ofG1⊝G2

Theorem 7.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 be an r2-regular graph on n2 vertices and m2 edges. Then the generalized characteristic polynomial of subdivision-edge-edge join of G1 and G2 is (23)ϕG1⊝G2x;t=∏i=1n1x2+m2t+2t+r1tx+r1m2t2+2r1t2-λiG1-r1·∏i=1n2x2+m1t+2t+r2tx+r2m1t2+2r2t2-λiG2-r2·1-m1m2x+r1tx+r2tx2+m1t+r2t+2tx+r2m1t2+2r2t2-2r2-1x2+m2t+r1t+2tx+r1m2t2+2r1t2-2r1·x+m1t+2tm2-n2x+m2t+2tm1-n1.Proof.
LetR1 be the incidence matrix of G1. Then, with respect to the adjacent matrix and degree matrix of G1⊝G2, the generalized matrix of G1⊝G2 is given by (24)AG1⊝G2-tDG1⊝G2=-r1tIn1R10n1×m20n1×n2R1T-m2+2tIm11m1×m20m1×n20m2×n11m2×m1-m1+2tIm2R2T0n2×n10n2×m1R2-r2tIn2.Thus the generalized characteristic polynomial of G1⊝G2 is (25)ϕG1⊝G2x;t=det⁡x+r1tIn1-R10n1×m20n1×n2-R1Tx+m2t+2tIm1-1m1×m20m1×n20m2×m1-1m2×m1x+m1t+2tIm2-R2T0n2×n10n2×m1-R2x+r2tIn2=det⁡x+r1tIn1det⁡S=x+r1tn1det⁡S,where(26)S=x+m2t+2tIm1-R1TR1x+r1t-1m1×m20m1×n2-1m2×m1x+m1t+2tIm2-R2T0n2×m1-R2x+r2tIn2is the Schur complement of x+r1tIn1. So, det⁡(S)=x+r2tn2det⁡(S1), where (27)S1=x+m2t+2tIm1-R1TR1x+r1t-1m1×m2-1m2×m1x+m1t+2tIm2-R2TR2x+r2tis the Schur complement of x+r2tIn2. So, (28)det⁡S1=det⁡x+m2t+2tIm1-R1TR1x+r1t·det⁡x+m1t+2tIm2-R2TR2x+r2t-1m2×m1x+m2t+2tIm1-R1TR1x+r1t-11m1×m2is the Schur complement of (x+m2t+2t)Im1-R1TR1/x+r1t. So,(29)ϕG1⊝G2x;t=x+r1tn1x+r2tn2det⁡x+m2t+2tIm1-AlG1+2Im1x+r1t·det⁡x+m1t+2tIm2-R2TR2x+r2t-1m2×m1x+m2t+2tIm1-R1TR1x+r1t-11m1×m2;by Lemma 4,(30)ϕG1⊝G2x;t=x+r1tn1x+r2tn2x+m2t+2tm1-n1∏i=1n1x+m2t+2t-λiG1+r1-2+2x+r1t·det⁡x+m1t+2tIm2-R2TR2x+r2t-ΓR1TR1/x+r1tx+m2t+2t1m2×m2and by Lemma 1,(31)ϕG1⊝G2x;t=x+r1tn1x+r2tn2x+m2t+2tm1-n1∏i=1n1x+m2t+2t-λiG1+r1x+r1t·1-ΓR1TR1/x+r1tx+m2t+2tΓR2TR2/x+r2tx+m1t+2tdet⁡x+m1t+2tIm2-R2TR2x+r2t=∏i=1n1x2+m2t+2t+r1tx+r1m2t2+2r1t2-λiG1-r1·∏i=1n2x2+m1t+2t+r2tx+r2m1t2+2r2t2-λiG2-r2·1-m1m2x+r1tx+r2tx2+m1t+r2t+2tx+r2m1t2+2r2t2-2r2-1x2+m2t+r1t+2tx+r1m2t2+2r1t2-2r1·x+m1t+2tm2-n2x+m2t+2tm1-n1.Theorem 8.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges. Then(1)
the adjacency characteristic polynomial ofG1⊝G2 is (32)ψAG1⊝G2;x=xm1+m2-n1-n2∏i=1n1x2-λiG1-r1∏i=1n2x2-λiG2-r2·1-m1m2x2x4-2r1+r2x2+4r1r2,(2)
the Laplacian characteristic polynomial ofG1⊝G2 is (33)ψLG1⊝G2;x=∏i=2n1x2-m2+2+r1x+r1m2+uiG1∏i=2n2x2-m1+2+r2x+r2m1+uiG2·x-m1-2m2-n2x-m2-2m1-n1·xx3-m1+m2+r1+r2+4x2+r1m2+r2m1+r2m2+r1m1+r1r2+2m1+2m2+2r1+2r2+4x-m1r1r2-m2r1r2-2m1r2-2m2r1,(3)
the signless Laplacian characteristic polynomial ofG1⊝G2 is (34)ψQG1⊝G2;x=∏i=1n1x2-m2+2+r1x+r1m2+2-νiG1x-m2-2m1-n1·1-m1m2x-r1x-r2x2-m2+r1+2x+m2r1x2-m1+r2+2x+m1r2·∏i=1n2x2-m1+2+r2x+r2m1+2-νiG2x-m1-2m2-n2.


## 5. Applications

We give the number of spanning trees, the Kirchhoff index, andLEL of the two classes of join graphs, as the applications.We can easily compute theL-spectrum of G1⊚G2 in terms of L-spectrum of G1 and G2 by (2) of Theorem 6.Corollary 9.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges. Then the Laplacian spectrum of G1⊚G2 consists of(1)
2, repeatedm1+m2-n1-n2 times;(2)
two roots of the equationx2-(r1+n2+2)x+2n2+μi(G1)=0, for each i=2,…,n1;(3)
two roots of the equationx2-(r2+n1+2)x+2n1+μi(G2)=0, for each i=2,…,n2;(4)
four roots of the equationx(x3-(n1+n2+r1+r2+4)x2 + (4n1+4n2+2r1+2r2+4+r1r2 + r1n1+r2n2)x-4n1-4n2-2n1r1-2n2r2)=0, and the four roots are 0, ω1, ω2, and ω3, respectively.We can easily compute the L-spectrum ofG1⊝G2 in terms of L-spectrum of G1 and G2 by (2) of Theorem 8.Corollary 10.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges. Then the Laplacian spectrum of G1⊝G2 consists of(1)
m1+2, repeated m2-n2 times;(2)
m2+2, repeated m1-n1 times;(3)
two roots of the equationx2-(m2+2+r1)x+r1m2+μi(G1)=0, for each i=2,…,n1;(4)
two roots of the equationx2-(m1+2+r2)x+r2m1+μi(G2)=0, for each i=2,…,n2;(5)
four roots of the equationx(x3-(m1+m2+r1+r2+4)x2 + (r1m2+r2m1+r2m2+r1m1+r1r2 + 2m1+2m2+2r1+2r2+4)x-m1r1r2-m2r1r2-2m1r2-2m2r1)=0, and the four roots are 0, γ1, γ2, and γ3, respectively.Lett(G) denote the number of spanning trees [1] of G. It is well known that if G is a connected graph on n vertices with Laplacian spectrum 0=μ1(G)≤μ2(G)≤⋯≤μn(G), then t(G)=μ2(G)⋯μn(G)/n.Corollary 11.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges. The number of spanning trees of G1⊚G2 and G1⊝G2 are, respectively, (35)tG1⊚G2=2m1+m2-n1-n2∏i=2n12n2+μiG1∏i=2n22n1+μiG24n1+4n2+2r1n1+2r2n2n1+m1+n2+m2,tG1⊝G2=m1+2m2-n2m2+2m1-n1∏i=2n1r1m2+μiG1∏i=2n2r2m1+μiG2n1+m1+n2+m2m1r1r2+m2r1r2+2m1r2+2m2r1-1.Proof.
ForG1⊚G2, the number of the vertices is n1+m1+n2+m2. By Corollary 9 and Vieta’s formulas, we can obtain the following: for every μi(G1), ∏i=2n1(x1x2)=∏i=2n1(2n2+μi(G1)); for every μi(G2), ∏i=2n2(x1x2)=∏i=2n2(2n1+μi(G2)); for the equation x3-(n1+n2+r1+r2+4)x2 + (4n1+4n2+2r1+2r2+4+r1r2+r1n1+r2n2)x-4n1-4n2-2n1r1-2n2r2=0, ω1ω2ω3=4n1+4n2+2r1n1+2r2n2. Therefore, we complete the proof of t(G1⊚G2) and we omit the proof of t(G1⊝G2).The Kirchhoff index [24] Kf(G) is an important physical and chemical indicator. Let G be a connected graph of order n; then Kf(G)=n∑i=2n1/μi.Corollary 12.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges; then the Kirchhoff index of G1⊚G2 and G1⊝G2 is, respectively, (36)KfG1⊚G2=m1+n1+m2+n2m1+m2-n1-n22+∑i=2n1r1+n2+22n2+μiG1+∑i=2n2r2+n1+22n1+μiG2+4n1+4n2+2r1+2r2+4+r1r2+r1n1+r2n24n1+4n2+2r1n1+2r2n2,KfG1⊝G2=m1+n1+m2+n2m2-n22+m1+m1-n12+m2+∑i=2n1m2+2+r1r1m2+μiG1+∑i=2n2m1+2+r2r2m1+μiG2+r1m2+r2m1+r2m2+r1m1+r1r2+2m1+2m2+2r1+2r2+4m1r1r2+m2r1r2+2m1r2+2m2r1.Proof.
ForG1⊚G2, by Corollary 9 and Vieta’s formulas, we can obtain the following: for every μi(G1), ∑i=2n1(1/x1+1/x2)=∑i=2n1‍x1+x2/x1x2=∑i=2n1‍r1+n2+2/2n2+μi(G1); for every μi(G2), ∑i=2n2(1/x1+1/x2)=∑i=2n2r2+n1+2/2n1+μi(G2); for the equation x3-(n1+n2 + r1+r2+4)x2 + (4n1+4n2+2r1+2r2+4+r1r2+r1n1+r2n2)x-4n1-4n2-2n1r1-2n2r2=0, 1/ω1+1/ω2+1/ω3 = ω1ω2+ω2ω3+ω1ω3/ω1ω2ω3 = 4n1+4n2+2r1+2r2+4+r1r2+r1n1+r2n2/4n1+4n2+2r1n1+2r2n2. Therefore, we complete the proof of Kf(G1⊚G2) and we omit the proof of Kf(G1⊝G2).L
E
L
(
G
) denotes Laplacian-Energy-Like Invariant [24]. Let G be a connected graph of order n with m edges; then LEL=LEL(G)=∑i=2nμi.Corollary 13.
LetG1 be an r1-regular graph on n1 vertices and m1 edges and G2 an r2-regular graph on n2 vertices and m2 edges; then (37)LELG1⊚G2=2m1+m2-n1-n2+∑i=13ωi+∑i=2n1r1+n2+2±Δ12+∑i=2n2r2+n1+2±Δ22,where Δ1=r1+n2+22-4(2n2+μi(G1)), Δ2=r2+n1+22-4(2n1+μi(G2)), and ω1, ω2, and ω3 are three roots of the equation x3-(n1+n2+r1+r2+4)x2 + (4n1+4n2+2r1+2r2+4+r1r2 + r1n1+r2n2)x-4n1-4n2-2n1r1-2n2r2=0. (38)LELG1⊝G2=m2-n2m1+2+m1-n1m2+2+∑i=13γi+∑i=2n1m2+2+r1±Δ32+∑i=2n2m1+2+r2±Δ42,where Δ3=m2+2+r12-4(r1m2+μi(G1)), Δ4=m1+2+r22-4(r2m1+μi(G2)), and γ1, γ2, and γ3 are three roots of the equation x3-(m1+m2+r1+r2+4)x2 + (r1m2+r2m1+r2m2+r1m1+r1r2+2m1 + 2m2+2r1+2r2+4)x-m1r1r2-m2r1r2 − 2m1r2-2m2r1=0.


## 6. Conclusions

In this paper, two classes of join graphs,G1⊚G2 and G1⊝G2, are constructed by graph operations. The formulas of generalized characteristic polynomial of the two graphs are obtained by using block matrix and Schur complement. For regular graphs G1 and G2, we characterize the A-, L-, and Q-spectrum of G1⊚G2 and G1⊝G2 in terms of the corresponding spectrum of G1 and G2, and by the L-spectrum, we get the number of spanning trees, Kirchhoff index, and LEL. But for nonregular graphs G1 and G2, we cannot determine the spectrum of G1⊚G2 and G1⊝G2. The most difficult problem is that we cannot find the rule of the block matrices to deduce a simple result. Therefore, we should try to find new method to solve the problem.



---

*Source: 2372931-2017-03-02.xml*