# On the Adjacency, Laplacian, and Signless Laplacian Spectrum of Coalescence of Complete Graphs

Authors: S. R. Jog; Raju Kotambari
Journal: Journal of Mathematics
 (2016)

---

## Abstract

Coalescence as one of the operations on a pair of graphs is significant due to its simple form of chromatic polynomial. The adjacency matrix, Laplacian matrix, and signless Laplacian matrix are common matrices usually considered for discussion under spectral graph theory. In this paper, we compute adjacency, Laplacian, and signless Laplacian energy (Q energy) of coalescence of pair of complete graphs. Also, as an application, we obtain the adjacency energy of subdivision graph and line graph of coalescence from its Q energy.


---

## Body

## 1. Introduction

Throughout the discussion by a graph we mean simple graph without self loops or multiple edges. LetG be a simple graph on n vertices with vertex setv1,v2,…,vn. The line graph of a graph G is the graph with vertex set as edge set of G with two vertices (edges ofG) adjacent if and only if they are having a vertex in common. Similarly, the subdivision graph of a graph G is the graph S(G) obtained by inserting a vertex of degree two in each edge of G. The adjacency matrix of G denoted by A(G) is a matrixA(G)=[aij], where aij=1 if vertex vi is adjacent to vj and 0 otherwise. Clearly, A(G) is real symmetric so that eigenvalues of A(G) which are roots of its characteristic equation given by P(G;λ)=λI-AG=0 are real. They are denoted by λ1,λ2,…,λn and can be arranged in descending order as λ1≥λ2≥⋯≥λn. The spectrum of G is collection of eigenvalues along with their multiplicity and energy of a graph is simply defined as ∑λi. For more details and rigorous treatment on adjacency spectra and energy, see [1–4]. Let di denote the degree of a vertex vi which is the number of edges incident on it. The degree matrix D is a diagonal matrix having diagonal entry as the degree of the corresponding vertex. We denote the average degree of a graph G, as avd(G)=twice the no edges ofG/no. of vertices ofG. The matrix C(G)=D(G)-A(G) is called Laplacian matrix. The roots of the characteristic polynomial of the Laplacian matrix are called Laplacian eigenvalues denoted by μ1,μ2,…,μn. The matrix C(G) is also real symmetric but singular so eigenvalues can be arranged as μ1≥μ2≥⋯≥μn=0. The Laplacian spectrum of G is the collection of Laplacian eigenvalues along with their multiplicity and Laplacian energy is defined as ELG=∑μi-avdG.For an extensive literature on Laplacian spectra and energy, one can refer to [5–11]. On similar lines, the signless Laplacian matrix of a graph G is defined as Q(G)=D(G)+A(G). The signless Laplacian eigenvalues are also real and can be denoted byv1,v2,…,vn. The signless Laplacian energy (or simply Q energy) is defined similar to Laplacian energy as ESLG=∑vi-avdG.Some results on signless Laplacian energy are available in [12–15]. The Laplacian and signless Laplacian eigenvalues for a connected graph are nonnegative.LetH1 and H2 be graphs on disjoint sets of vertices, respectively. Suppose U={u1,u2,…,ut} is a clique in H1 and W=w1,w2,…,wt is a clique in H2. Let G be a graph obtained from H1 and H2 by identifying (coalescing into a single vertex) ui and wi1≤i≤t. Then, G is an overlap of H1 and H2 in Kt. It may be viewed as generalized coalescence denoted by H1∘H2.The structure ofH1∘H2 depends on vertices chosen for overlap. Its chromatic polynomial can be split into chromatic polynomials of H1 and H2 (see [16]). If t=1, we call it vertex coalescence denoted by H1∘vH2 and for t=2 we call it edge coalescence denoted by H1∘eH2. For vertex coalescence of two graphs H1 and H2, the adjacency matrix has the form(1)AH1∘vH2=0JJJTAH1-uOJTOAH2-v.Similarly, the edge coalescence of two graphsG1 and G2 has the adjacency matrix structure(2)AH1∘eH2=AK2JJJTAH1-eOJTOAH2-e,where J is matrix of all 1’s and O is the matrix of all zeros having appropriate order.


## 2. Results

### 2.1. Adjacency Energy

Theorem 1.
The energy (adjacency energy) ofKm∘vKn is given by E[Km∘vKn]=(m+n-4)+α+β+δ, where α, β, and δ are the roots of the cubic: (3)x3-m+n-4x2+mn-3m-3n+6x+2mn-3m-3n+4=0.Proof.
The coalescence of the complete graphsKm and Kn at a point results in a graph with m+n-1 vertices and (mC2+nC2) edges. The adjacency matrix takes the form (4)AKm∘vKn=0J1×m-1J1×n-1Jm-1×1AKm-1OJn-1×1OAKn-1so that characteristic polynomial is(5)PKm∘vKn:λ=λI-AKm∘vKn=λ-J1×m-1-J1×n-1-Jm-1×1λIm-1-AKm-1O-Jn-1×1OλIn-1-AKn-1.By performingC1+∑i=2m-1Ci/λ-m-2 and C1+∑j=m+1m+n-1Cj/λ-n-2in succession, we have(6)PKm∘vKn:λ=λ-m-1λ-m-2-n-1λ-n-2PKm-1:λPKn-1:λ=λ-m-1λ-m-2-n-1λ-n-2λ-m-2λ+1m-2λ-n-2λ+1n-2.On simplifying, finally we get(7)PKm∘vKn:λ:λ+1m+n-4λ3-m+n-4λ2+mn-3m-3n+6λ+m-1n-2+n-1m-2.From this equation, the theorem follows.Theorem 2.
The energy (adjacency energy) of edge coalescenceKm∘eKn of complete graphs is given by EKm∘eKn=m+n-5+α+β+δ, where α, β, and δ are the roots of the cubic equation: (8)x3-m+n-5x2+mn-4m-4n+11x+3mn-7m-7n+15=0.Proof.
The coalescence of the complete graphsKm and Kn on an edge results in a graph with m+n-2 vertices and mC2+nC2-1 edges. The adjacency matrix takes the form(9)AKm∘eKn=AK2J2×m-2J2×n-2Jm-2×2AKm-eOJn-2×2OAKn-eso that the characteristic polynomial of the edge coalescence is(10)PKm∘eKn:λ=λI-AKm∘eKn=λI-AK2-J2×m-2-J2×n-2-Jm-2×2λI-AKm-eO-Jn-2×2OλI-AKn-e.By performingCj+∑i=3mCi/λ-m+3 for j=1,2we have(11)
P
K
m
∘
e
K
n
:
λ
=
λ
-
m
-
2
λ
-
m
+
3
-
1
-
m
-
2
-
m
+
3
-
J
1
×
m
-
2
-
J
1
×
n
-
2
-
1
-
m
-
2
-
m
+
3
λ
-
m
-
2
λ
-
m
+
3
-
J
1
×
m
-
2
-
J
1
×
n
-
2
O
O
λ
I
-
A
K
m
-
2
O
-
J
n
-
2
×
1
-
J
n
-
2
×
1
O
λ
I
-
A
K
n
-
2
.By performingCj+∑i=m+1m+n-2Ci/(λ-n+3) for j=1,2we have(12)
P
K
m
∘
e
K
n
:
λ
=
λ
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
-
1
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
-
J
1
×
m
-
2
-
J
1
×
n
-
2
-
1
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
λ
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
-
J
1
×
n
-
2
-
J
1
×
n
-
2
O
O
λ
I
-
A
K
m
-
2
O
O
O
O
λ
I
-
A
K
n
-
2
=
λ
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
2
-
-
1
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
2
P
K
m
-
2
:
λ
P
K
n
-
2
:
λ
.On expanding and simplifying, we get the required polynomial and hence the theorem.


### 2.2. Laplacian Energy

Now we discuss the Laplacian energy of coalescence.Lemma 3 (see [17]).
If G is any connected graph of order n with Laplacian eigenvaluesμ1,μ2,…,μn with μn=0, then, the number of spanning trees of G is given by(13)τG=μ1,μ2,…,μn-1n.Theorem 4.
The Laplacian energy of the vertex coalescence of complete graphsKm and Kn is given by(14)ELKm∘vKn=3m2+3n2-5m-5n+1m+n-1.Proof.
The degree matrix of the vertex coalescenceKm∘vKn with suitable labeling has the form(15)DKm∘vKn=m+n-20⋯⋯000⋯00m-10⋯000⋯000m-1⋯000⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮000⋯m-10000000⋯0n-1000000⋯00n-100⋮⋮⋮⋮⋮⋮⋮⋱⋮0000000⋯n-1The adjacency matrix is(16)AKm∘vKn=OJJJTAKm-1OJTOAKn-1.The Laplacian matrix now becomes(17)CKm∘vKn=m+n-2-1-1⋯-1-1-1⋯-1-1m-1-1⋯-100⋯0-1-1m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯m-100⋯0-100⋯0n-1-1⋯-1-100⋯0-1n-1⋯-1⋮⋮⋮⋮⋮⋮⋮⋱⋮-10000-1-1⋯n-1so that the Laplacian polynomial is(18)μI-CKm∘vKn=μ-m+n-211⋯111⋯11μ-m-11⋯100⋯011μ-m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯μ-m-100⋯0100⋯0μ-m-1000100⋯00μ-m-100⋮⋮⋮⋮⋮⋮⋮⋱⋮1000000⋯μ-m-1.PerformingC1-1/μ-1∑i=2nCiwe get (19)μI-CKm∘vKn=μ-m+n-2-m-1λ-111⋯111⋯11μ-m-11⋯100⋯011μ-m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯μ-m-100⋯0100⋯0μ-m-1000100⋯00μ-m-100⋮⋮⋮⋮⋮⋮⋮⋱⋮1000000⋯μ-m-1.Again performingC1-1/μ-1∑i=m+1m+n-1Ciand directly expanding along first column, we get(20)μI-CKm∘vKn=μ-m+n-2-n-1μ-1-m-1μ-1LKm-1:λLKn-1:λ=μμ-m+n-1μ-1μ-mm-2μ-nn-2.So that the Laplacian spectrum is SLKm∘vKn=m,m-2times, n,n-2 times, m+n-1, 1, and 0.
Now the avdKm∘vKn=mm-1+nn-1/m+n-1;hence, the Laplacian energy becomes(21)ELKm∘vKn=∑i=1m+n-1μi-mm-1+nn-1m+n-1=m-mm-1+nn-1m+n-1m-2+n-mm-1+nn-1m+n-1n-2+m+n-1-mm-1+nn-1m+n-1+1-mm-1+nn-1m+n-1+0-mm-1+nn-1m+n-1=3m2+3n2-5m-5n+1m+n-1.Corollary 5.
The number of spanning trees ofKm∘vKn according to Lemma 3 isτ(Km∘vKn)=m(m-2)n(n-2)(m+n-1)/(m+n-1)=m(m-2)n(n-2) as expected since Km∘vKn has a cut point with number of spanning trees mm-2 and nn-2 in each block (complete graph) separately.Theorem 6.
The Laplacian energy of the edge coalescence of complete graphsKm and Kn is given by(22)ELKm∘eKn=m-nm-1+2m+n-2m-3+n-mm-1+2m+n-2n-3+α-m2+n2-m-n-2m+n-2+β-m2+n2-m-n-2m+n-2+δ-m2+n2-m-n-2m+n-2,where α, β, and δ are the roots of the cubic equation: (23)x3-2m+n-1x2+m2+n2+2mn-4x-2m+n-22=0.Proof.
The degree matrix of the edge coalescence(Km∘eKn) with suitable labeling has the form(24)DKm∘eKn=m+n-30⋯⋯000⋯00m+n-30⋯000⋯000m-1⋯000⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮000⋯m-10000000⋯0n-1000000⋯00n-100⋮⋮⋮⋮⋮⋮⋮⋱⋮0000000⋯n-1.The adjacency matrix is(25)AKm∘eKn=O1J1×m-2J1×n-210J1×m-2J1×n-2Jm-2×1Jm-2×1AKm-2OJn-2×1Jn-2×1OAKn-2.CKm∘vKn=m+n-3-1-1⋯-1-1-1⋯-1-1m+n-3-1⋯-1-1-1⋯-1-1-1m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯m-100⋯0-1-10⋯0n-1-1⋯-1-1-10⋯0-1n-1⋯-1⋮⋮⋮⋮⋮⋮⋮⋱⋮-1-10⋯0-1-1⋯n-1The Laplacian polynomial is then given by(26)μI-CKm∘eKn=μ-m+n-31⋯⋯111⋯11μ-m+n-31⋯111⋯111μ-m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯μ-m-100⋯0110⋯0μ-n-11⋯1110⋯01μ-n-1⋯1⋮⋮⋮⋮⋮⋮⋮⋱⋮110⋯011⋯μ-n-1.PerformingC1-1/μ-2∑i=3mCiandC2-1/μ-2∑i=3mCi,(27)μI-CKm∘eKn=μ-m+n-3-m-2μ-21-m-2μ-2⋯⋯111⋯11-m-2μ-2μ-m+n-3-m-2μ-21⋯111⋯111μ-m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯μ-m-100⋯0110⋯0μ-n-11⋯1110⋯01μ-n-1⋯1⋮⋮⋮⋮⋮⋮⋮⋱⋮110⋯011⋯μ-n-1Again performingC1-1/μ-2∑i=m+1m+n-2CiandC2-1/μ-2∑i=m+1m+n-2Ci and directly expanding give(28)
μ
I
-
C
K
m
∘
e
K
n
=
μ
-
m
+
n
-
3
-
m
+
n
-
4
μ
-
2
1
-
m
+
n
-
4
μ
-
2
1
-
m
+
n
-
4
μ
-
2
μ
-
m
+
n
-
3
-
m
+
n
-
4
μ
-
2
L
K
m
-
2
:
μ
L
K
n
-
2
:
μ
.On simplifying, we get the Laplacian polynomial as(29)μI-CKm∘eKn=μμ-mm-3μ-nn-3μ3-2m+n-1μ2+m2+n2+2mn-4μ-2m+n-22.On equating to zero and extracting eigenvalues from the equation above, the theorem follows.
Note. When m=n, the Laplacian polynomial is(30)μI-CKn∘eKn=μ-n2n-3μ3-22n-1μ2+4n2-4μ-8n-12=μ-n2n-3μ-2μ-2n-12.The Laplacian eigenvalues are n, 2n-3 times, 2(n-1) twice, 2, and 0 once.
Sinceadg(Km∘eKn)=n2-n-1/(2n-2)the Laplacian energy is(31)ELKn∘eKn=0-n2-n-12n-2+2-n2-n-12n-2+n-n2-n-12n-22n-3+2n-1-n2-n-12n-2×2=2n3+n2-5n+62n-2forn=2,3,4,=2n3+3n2-15n+92n-2forn≥5.


### 2.3. Signless Laplacian Energy

Now we consider the case of signless Laplacian matrix of the coalescence of complete graphs and deduce the corresponding energy. Before we do so, consider the following results.Lemma 7 (see [17]).
If G is any graph with p vertices and q edges, then characteristic polynomial of line graphL(G) in terms of Q (signless Laplacian) polynomial is given by(32)PLG:λ=λ+2q-pQG:λ+2.Lemma 8 (see [18]).
If G is any graph with p vertices and q edges, then characteristic polynomial of subdivision graphS(G) in terms of Q (signless Laplacian) polynomial is given by(33)PSG:λ=λq-pQG:λ2.Theorem 9.
The signless Laplacian energy of the vertex coalescence of complete graphsKm and Kn is given by(34)ESLKm∘vKn=mn-3m-n+5m-2+mn-3n-m+5n-2+2mn-3.5m-3.5n+6+a+2mn-3.5m+3.5n+6-a+2mn-m-n+7m+n-2,where a=(m-n)2+m+n-1.75.Proof.
From the degree matrix and adjacency matrix of the vertex coalescence(Km∘vKn),we have the signless Laplacian matrix:(35)QKm∘vKn=m+n-21⋯⋯111⋯11m-11⋯111⋯111m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯m-100⋯0100⋯0n-11⋯1100⋯01n-1⋯1⋮⋮⋮⋮⋮⋮⋮⋱⋮100⋯011⋯n-1.The signless Laplacian polynomial is then(36)νI-QKm∘vKn=ν-m+n-2-1-1⋯-1-1-1⋯-1-1ν-m-1-1⋯-1-1-1⋯-1-1-1ν-m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯ν-m-100⋯-1-100⋯0ν-n-1-1⋯-1-100⋯0-1ν-n-1⋯0⋮⋮⋮⋮⋮⋮⋮⋱⋮-100⋯0-1-1⋯ν-n-1.PerformingC1+1/ν-2m+3∑i=2nCi,(37)νI-QKm∘vKn=ν-m+n-2-m-1ν-m-1-1-1⋯-1-1-1⋯-1-1ν-m-1-1⋯-1-1-1⋯-1-1-1ν-m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯ν-m-100⋯-1-100⋯0ν-n-1-1⋯-1-100⋯0-1ν-n-1⋯0⋮⋮⋮⋮⋮⋮⋮⋱⋮-100⋯0-1-1⋯ν-n-1.Again performingC1+1/ν-2m+3∑j=m+1m+n-1Cjthen directly expanding along first column, we obtain(38)νI-QKm∘vKn=ν-m+n-3ν-m-2m-2ν-n-2n-2ν2-2m+2n-5ν+4mn-6m-6n+8.
The signless Laplacian eigenvalues arem-2(m-2) times,(n-2)(n-2) times,m+n-2.5±m-n2+m+n-1.75, and m+n-3.
Now theadgKm∘eKn=mm-1+nn-1-1/m+n-2;hence, the theorem follows.Corollary 10.
From Lemma7, the energy (adjacency energy) of line graph of Km∘vKn is given by (39)ELKm∘vKn=m2+n2-3m-3n+2+m-2m-4+n-2n-4+2m+2n-9m,n≥3.
In particular form,n≥4,(40)ELKm∘vKn=2m-22+2n-22-3+2m-n2+m+n-1.75.Corollary 11.
From Lemma8, the energy (adjacency) of subdivision graph of Km∘vKn where m,n≥2, is given by (41)ESKm∘vKn=2m+n-3+2m-2m-2+2n-2n-2+22m+2n-5±2m2+n2-11m-11n-8.Theorem 12.
The signless Laplacian energy of the edge coalescence of complete graphsKm and Kn is given by(42)ESLKm∘eKn=2mn-5m-5n+10m+n-2m+n-2+mn-n2-3m-n+6m+n-2m-3+mn-m2-3n-m+6m+n-2n-3+α-m2+n2-m-n-2m+n-2+β-m2+n2-m-n-2m+n-2+δ-m2+n2-m-n-2m+n-2,where α,β, and δ are roots of the cubic equation: (43)x3-3m+3n-10x2+2m2+n2+4mn-11m-11n+20x-4m+n-4m-2n-2=0.Proof.
From the degree and adjacency matrix, the signless Laplacian matrix of the edge coalescence is(44)QKm∘eKn=m+n-31⋯⋯111⋯11m+n-31⋯111⋯111m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯m-100⋯0110⋯0n-11⋯1110⋯01n-1⋯1⋮⋮⋮⋮⋮⋮⋮⋱⋮110⋯011⋯n-1.The signless Laplacian polynomial is then given by(45)νI-QKm∘eKn=ν-m+n-3-1⋯⋯-1-1-1⋯-1-1ν-m+n-3-1⋯-1-1-1⋯-1-1-1ν-m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯ν-m-100⋯0-1-10⋯0ν-n-11⋯-1-1-10⋯0-1ν-n-1⋯-1⋮⋮⋮⋮⋮⋮⋮⋱⋮-1-10⋯0-1-1⋯ν-n-1.PerformingC1,C2+1/ν-2m+4∑i=3mCi,(46)νI-QKm∘eKn=ν-m+n-3-m-2ν-2m+4-1-m-2ν-2m+4⋯⋯-1-1-1⋯-1-1-m-2ν-2m+4ν-m+n-3-m-2ν-2m+4-1⋯-1-1-1⋯-100ν-m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮00-1⋯ν-m-100⋯0-1-10⋯0ν-n-1-1⋯-1-1-10⋯0-1ν-n-1⋯-1⋮⋮⋮⋮⋮⋮⋮⋱⋮-1-10⋯0-1-1⋯ν-n-1.Again performingC1,C2+1/ν-2∑j=3m+n-2Cjand expanding directly yield(47)
ν
I
-
Q
K
m
∘
e
K
n
=
Q
K
m
-
2
:
ν
Q
K
n
-
2
:
ν
ν
-
m
+
n
-
3
-
m
-
2
ν
-
2
m
+
4
-
n
-
2
ν
-
2
n
+
4
-
1
-
m
-
2
ν
-
2
m
+
4
-
n
-
2
ν
-
2
n
+
4
-
1
-
m
-
2
ν
-
2
m
+
4
-
n
-
2
ν
-
2
n
+
4
ν
-
m
+
n
-
3
-
m
-
2
ν
-
2
m
+
4
-
n
-
2
ν
-
2
n
+
4
.On performing elementary operations, we finally arrive at(48)νI-QKm∘eKn=ν-m+n-4ν-m-2m-3ν-n-2n-3ν3-3m+3n-10ν2+2m2+n2+4mn-11m-11n+20ν-4m+n-4m-2n-2.On equating to zero and extracting eigenvalues from the equation above, the theorem follows.Corollary 13.
From Lemma7, the energy (adjacency) of line graph of Km∘eKn is given by(49)ELKm∘eKn=m2+n2-3m-3n+2+m+n-6+m-4m-3+n-4n-3+λ1+λ2+λ3,where, λ1, λ2, and λ3 are the roots of the cubic equation:(50)λ3-3m+3n-16λ2+2m2+2n2+8mn-34m-34n+92λ+4m2+n2+4mn-14m-14n+32-m+n-4mn-2m-2n+4=0.Corollary 14.
From Lemma8, the energy (adjacency) of subdivision graph of Km∘eKn where m,n≥2 is given by(51)ESKm∘eKn=2m+n-4+2m-2m-3+2n-2n-3+λ1+λ2+λ3, where λ1, λ2, and λ3 are the roots of the equation(52)λ3-3m+3n-10λ2+2m2+n2+4mn-11m-11n+20λ-4m+n-4m-2n-2=0.


## 2.1. Adjacency Energy

Theorem 1.
The energy (adjacency energy) ofKm∘vKn is given by E[Km∘vKn]=(m+n-4)+α+β+δ, where α, β, and δ are the roots of the cubic: (3)x3-m+n-4x2+mn-3m-3n+6x+2mn-3m-3n+4=0.Proof.
The coalescence of the complete graphsKm and Kn at a point results in a graph with m+n-1 vertices and (mC2+nC2) edges. The adjacency matrix takes the form (4)AKm∘vKn=0J1×m-1J1×n-1Jm-1×1AKm-1OJn-1×1OAKn-1so that characteristic polynomial is(5)PKm∘vKn:λ=λI-AKm∘vKn=λ-J1×m-1-J1×n-1-Jm-1×1λIm-1-AKm-1O-Jn-1×1OλIn-1-AKn-1.By performingC1+∑i=2m-1Ci/λ-m-2 and C1+∑j=m+1m+n-1Cj/λ-n-2in succession, we have(6)PKm∘vKn:λ=λ-m-1λ-m-2-n-1λ-n-2PKm-1:λPKn-1:λ=λ-m-1λ-m-2-n-1λ-n-2λ-m-2λ+1m-2λ-n-2λ+1n-2.On simplifying, finally we get(7)PKm∘vKn:λ:λ+1m+n-4λ3-m+n-4λ2+mn-3m-3n+6λ+m-1n-2+n-1m-2.From this equation, the theorem follows.Theorem 2.
The energy (adjacency energy) of edge coalescenceKm∘eKn of complete graphs is given by EKm∘eKn=m+n-5+α+β+δ, where α, β, and δ are the roots of the cubic equation: (8)x3-m+n-5x2+mn-4m-4n+11x+3mn-7m-7n+15=0.Proof.
The coalescence of the complete graphsKm and Kn on an edge results in a graph with m+n-2 vertices and mC2+nC2-1 edges. The adjacency matrix takes the form(9)AKm∘eKn=AK2J2×m-2J2×n-2Jm-2×2AKm-eOJn-2×2OAKn-eso that the characteristic polynomial of the edge coalescence is(10)PKm∘eKn:λ=λI-AKm∘eKn=λI-AK2-J2×m-2-J2×n-2-Jm-2×2λI-AKm-eO-Jn-2×2OλI-AKn-e.By performingCj+∑i=3mCi/λ-m+3 for j=1,2we have(11)
P
K
m
∘
e
K
n
:
λ
=
λ
-
m
-
2
λ
-
m
+
3
-
1
-
m
-
2
-
m
+
3
-
J
1
×
m
-
2
-
J
1
×
n
-
2
-
1
-
m
-
2
-
m
+
3
λ
-
m
-
2
λ
-
m
+
3
-
J
1
×
m
-
2
-
J
1
×
n
-
2
O
O
λ
I
-
A
K
m
-
2
O
-
J
n
-
2
×
1
-
J
n
-
2
×
1
O
λ
I
-
A
K
n
-
2
.By performingCj+∑i=m+1m+n-2Ci/(λ-n+3) for j=1,2we have(12)
P
K
m
∘
e
K
n
:
λ
=
λ
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
-
1
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
-
J
1
×
m
-
2
-
J
1
×
n
-
2
-
1
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
λ
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
-
J
1
×
n
-
2
-
J
1
×
n
-
2
O
O
λ
I
-
A
K
m
-
2
O
O
O
O
λ
I
-
A
K
n
-
2
=
λ
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
2
-
-
1
-
m
-
2
λ
-
m
+
3
-
n
-
2
λ
-
n
+
3
2
P
K
m
-
2
:
λ
P
K
n
-
2
:
λ
.On expanding and simplifying, we get the required polynomial and hence the theorem.


## 2.2. Laplacian Energy

Now we discuss the Laplacian energy of coalescence.Lemma 3 (see [17]).
If G is any connected graph of order n with Laplacian eigenvaluesμ1,μ2,…,μn with μn=0, then, the number of spanning trees of G is given by(13)τG=μ1,μ2,…,μn-1n.Theorem 4.
The Laplacian energy of the vertex coalescence of complete graphsKm and Kn is given by(14)ELKm∘vKn=3m2+3n2-5m-5n+1m+n-1.Proof.
The degree matrix of the vertex coalescenceKm∘vKn with suitable labeling has the form(15)DKm∘vKn=m+n-20⋯⋯000⋯00m-10⋯000⋯000m-1⋯000⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮000⋯m-10000000⋯0n-1000000⋯00n-100⋮⋮⋮⋮⋮⋮⋮⋱⋮0000000⋯n-1The adjacency matrix is(16)AKm∘vKn=OJJJTAKm-1OJTOAKn-1.The Laplacian matrix now becomes(17)CKm∘vKn=m+n-2-1-1⋯-1-1-1⋯-1-1m-1-1⋯-100⋯0-1-1m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯m-100⋯0-100⋯0n-1-1⋯-1-100⋯0-1n-1⋯-1⋮⋮⋮⋮⋮⋮⋮⋱⋮-10000-1-1⋯n-1so that the Laplacian polynomial is(18)μI-CKm∘vKn=μ-m+n-211⋯111⋯11μ-m-11⋯100⋯011μ-m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯μ-m-100⋯0100⋯0μ-m-1000100⋯00μ-m-100⋮⋮⋮⋮⋮⋮⋮⋱⋮1000000⋯μ-m-1.PerformingC1-1/μ-1∑i=2nCiwe get (19)μI-CKm∘vKn=μ-m+n-2-m-1λ-111⋯111⋯11μ-m-11⋯100⋯011μ-m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯μ-m-100⋯0100⋯0μ-m-1000100⋯00μ-m-100⋮⋮⋮⋮⋮⋮⋮⋱⋮1000000⋯μ-m-1.Again performingC1-1/μ-1∑i=m+1m+n-1Ciand directly expanding along first column, we get(20)μI-CKm∘vKn=μ-m+n-2-n-1μ-1-m-1μ-1LKm-1:λLKn-1:λ=μμ-m+n-1μ-1μ-mm-2μ-nn-2.So that the Laplacian spectrum is SLKm∘vKn=m,m-2times, n,n-2 times, m+n-1, 1, and 0.
Now the avdKm∘vKn=mm-1+nn-1/m+n-1;hence, the Laplacian energy becomes(21)ELKm∘vKn=∑i=1m+n-1μi-mm-1+nn-1m+n-1=m-mm-1+nn-1m+n-1m-2+n-mm-1+nn-1m+n-1n-2+m+n-1-mm-1+nn-1m+n-1+1-mm-1+nn-1m+n-1+0-mm-1+nn-1m+n-1=3m2+3n2-5m-5n+1m+n-1.Corollary 5.
The number of spanning trees ofKm∘vKn according to Lemma 3 isτ(Km∘vKn)=m(m-2)n(n-2)(m+n-1)/(m+n-1)=m(m-2)n(n-2) as expected since Km∘vKn has a cut point with number of spanning trees mm-2 and nn-2 in each block (complete graph) separately.Theorem 6.
The Laplacian energy of the edge coalescence of complete graphsKm and Kn is given by(22)ELKm∘eKn=m-nm-1+2m+n-2m-3+n-mm-1+2m+n-2n-3+α-m2+n2-m-n-2m+n-2+β-m2+n2-m-n-2m+n-2+δ-m2+n2-m-n-2m+n-2,where α, β, and δ are the roots of the cubic equation: (23)x3-2m+n-1x2+m2+n2+2mn-4x-2m+n-22=0.Proof.
The degree matrix of the edge coalescence(Km∘eKn) with suitable labeling has the form(24)DKm∘eKn=m+n-30⋯⋯000⋯00m+n-30⋯000⋯000m-1⋯000⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮000⋯m-10000000⋯0n-1000000⋯00n-100⋮⋮⋮⋮⋮⋮⋮⋱⋮0000000⋯n-1.The adjacency matrix is(25)AKm∘eKn=O1J1×m-2J1×n-210J1×m-2J1×n-2Jm-2×1Jm-2×1AKm-2OJn-2×1Jn-2×1OAKn-2.CKm∘vKn=m+n-3-1-1⋯-1-1-1⋯-1-1m+n-3-1⋯-1-1-1⋯-1-1-1m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯m-100⋯0-1-10⋯0n-1-1⋯-1-1-10⋯0-1n-1⋯-1⋮⋮⋮⋮⋮⋮⋮⋱⋮-1-10⋯0-1-1⋯n-1The Laplacian polynomial is then given by(26)μI-CKm∘eKn=μ-m+n-31⋯⋯111⋯11μ-m+n-31⋯111⋯111μ-m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯μ-m-100⋯0110⋯0μ-n-11⋯1110⋯01μ-n-1⋯1⋮⋮⋮⋮⋮⋮⋮⋱⋮110⋯011⋯μ-n-1.PerformingC1-1/μ-2∑i=3mCiandC2-1/μ-2∑i=3mCi,(27)μI-CKm∘eKn=μ-m+n-3-m-2μ-21-m-2μ-2⋯⋯111⋯11-m-2μ-2μ-m+n-3-m-2μ-21⋯111⋯111μ-m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯μ-m-100⋯0110⋯0μ-n-11⋯1110⋯01μ-n-1⋯1⋮⋮⋮⋮⋮⋮⋮⋱⋮110⋯011⋯μ-n-1Again performingC1-1/μ-2∑i=m+1m+n-2CiandC2-1/μ-2∑i=m+1m+n-2Ci and directly expanding give(28)
μ
I
-
C
K
m
∘
e
K
n
=
μ
-
m
+
n
-
3
-
m
+
n
-
4
μ
-
2
1
-
m
+
n
-
4
μ
-
2
1
-
m
+
n
-
4
μ
-
2
μ
-
m
+
n
-
3
-
m
+
n
-
4
μ
-
2
L
K
m
-
2
:
μ
L
K
n
-
2
:
μ
.On simplifying, we get the Laplacian polynomial as(29)μI-CKm∘eKn=μμ-mm-3μ-nn-3μ3-2m+n-1μ2+m2+n2+2mn-4μ-2m+n-22.On equating to zero and extracting eigenvalues from the equation above, the theorem follows.
Note. When m=n, the Laplacian polynomial is(30)μI-CKn∘eKn=μ-n2n-3μ3-22n-1μ2+4n2-4μ-8n-12=μ-n2n-3μ-2μ-2n-12.The Laplacian eigenvalues are n, 2n-3 times, 2(n-1) twice, 2, and 0 once.
Sinceadg(Km∘eKn)=n2-n-1/(2n-2)the Laplacian energy is(31)ELKn∘eKn=0-n2-n-12n-2+2-n2-n-12n-2+n-n2-n-12n-22n-3+2n-1-n2-n-12n-2×2=2n3+n2-5n+62n-2forn=2,3,4,=2n3+3n2-15n+92n-2forn≥5.


## 2.3. Signless Laplacian Energy

Now we consider the case of signless Laplacian matrix of the coalescence of complete graphs and deduce the corresponding energy. Before we do so, consider the following results.Lemma 7 (see [17]).
If G is any graph with p vertices and q edges, then characteristic polynomial of line graphL(G) in terms of Q (signless Laplacian) polynomial is given by(32)PLG:λ=λ+2q-pQG:λ+2.Lemma 8 (see [18]).
If G is any graph with p vertices and q edges, then characteristic polynomial of subdivision graphS(G) in terms of Q (signless Laplacian) polynomial is given by(33)PSG:λ=λq-pQG:λ2.Theorem 9.
The signless Laplacian energy of the vertex coalescence of complete graphsKm and Kn is given by(34)ESLKm∘vKn=mn-3m-n+5m-2+mn-3n-m+5n-2+2mn-3.5m-3.5n+6+a+2mn-3.5m+3.5n+6-a+2mn-m-n+7m+n-2,where a=(m-n)2+m+n-1.75.Proof.
From the degree matrix and adjacency matrix of the vertex coalescence(Km∘vKn),we have the signless Laplacian matrix:(35)QKm∘vKn=m+n-21⋯⋯111⋯11m-11⋯111⋯111m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯m-100⋯0100⋯0n-11⋯1100⋯01n-1⋯1⋮⋮⋮⋮⋮⋮⋮⋱⋮100⋯011⋯n-1.The signless Laplacian polynomial is then(36)νI-QKm∘vKn=ν-m+n-2-1-1⋯-1-1-1⋯-1-1ν-m-1-1⋯-1-1-1⋯-1-1-1ν-m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯ν-m-100⋯-1-100⋯0ν-n-1-1⋯-1-100⋯0-1ν-n-1⋯0⋮⋮⋮⋮⋮⋮⋮⋱⋮-100⋯0-1-1⋯ν-n-1.PerformingC1+1/ν-2m+3∑i=2nCi,(37)νI-QKm∘vKn=ν-m+n-2-m-1ν-m-1-1-1⋯-1-1-1⋯-1-1ν-m-1-1⋯-1-1-1⋯-1-1-1ν-m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯ν-m-100⋯-1-100⋯0ν-n-1-1⋯-1-100⋯0-1ν-n-1⋯0⋮⋮⋮⋮⋮⋮⋮⋱⋮-100⋯0-1-1⋯ν-n-1.Again performingC1+1/ν-2m+3∑j=m+1m+n-1Cjthen directly expanding along first column, we obtain(38)νI-QKm∘vKn=ν-m+n-3ν-m-2m-2ν-n-2n-2ν2-2m+2n-5ν+4mn-6m-6n+8.
The signless Laplacian eigenvalues arem-2(m-2) times,(n-2)(n-2) times,m+n-2.5±m-n2+m+n-1.75, and m+n-3.
Now theadgKm∘eKn=mm-1+nn-1-1/m+n-2;hence, the theorem follows.Corollary 10.
From Lemma7, the energy (adjacency energy) of line graph of Km∘vKn is given by (39)ELKm∘vKn=m2+n2-3m-3n+2+m-2m-4+n-2n-4+2m+2n-9m,n≥3.
In particular form,n≥4,(40)ELKm∘vKn=2m-22+2n-22-3+2m-n2+m+n-1.75.Corollary 11.
From Lemma8, the energy (adjacency) of subdivision graph of Km∘vKn where m,n≥2, is given by (41)ESKm∘vKn=2m+n-3+2m-2m-2+2n-2n-2+22m+2n-5±2m2+n2-11m-11n-8.Theorem 12.
The signless Laplacian energy of the edge coalescence of complete graphsKm and Kn is given by(42)ESLKm∘eKn=2mn-5m-5n+10m+n-2m+n-2+mn-n2-3m-n+6m+n-2m-3+mn-m2-3n-m+6m+n-2n-3+α-m2+n2-m-n-2m+n-2+β-m2+n2-m-n-2m+n-2+δ-m2+n2-m-n-2m+n-2,where α,β, and δ are roots of the cubic equation: (43)x3-3m+3n-10x2+2m2+n2+4mn-11m-11n+20x-4m+n-4m-2n-2=0.Proof.
From the degree and adjacency matrix, the signless Laplacian matrix of the edge coalescence is(44)QKm∘eKn=m+n-31⋯⋯111⋯11m+n-31⋯111⋯111m-1⋯100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮111⋯m-100⋯0110⋯0n-11⋯1110⋯01n-1⋯1⋮⋮⋮⋮⋮⋮⋮⋱⋮110⋯011⋯n-1.The signless Laplacian polynomial is then given by(45)νI-QKm∘eKn=ν-m+n-3-1⋯⋯-1-1-1⋯-1-1ν-m+n-3-1⋯-1-1-1⋯-1-1-1ν-m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮-1-1-1⋯ν-m-100⋯0-1-10⋯0ν-n-11⋯-1-1-10⋯0-1ν-n-1⋯-1⋮⋮⋮⋮⋮⋮⋮⋱⋮-1-10⋯0-1-1⋯ν-n-1.PerformingC1,C2+1/ν-2m+4∑i=3mCi,(46)νI-QKm∘eKn=ν-m+n-3-m-2ν-2m+4-1-m-2ν-2m+4⋯⋯-1-1-1⋯-1-1-m-2ν-2m+4ν-m+n-3-m-2ν-2m+4-1⋯-1-1-1⋯-100ν-m-1⋯-100⋯0⋮⋮⋮⋱⋮⋮⋮⋮⋮00-1⋯ν-m-100⋯0-1-10⋯0ν-n-1-1⋯-1-1-10⋯0-1ν-n-1⋯-1⋮⋮⋮⋮⋮⋮⋮⋱⋮-1-10⋯0-1-1⋯ν-n-1.Again performingC1,C2+1/ν-2∑j=3m+n-2Cjand expanding directly yield(47)
ν
I
-
Q
K
m
∘
e
K
n
=
Q
K
m
-
2
:
ν
Q
K
n
-
2
:
ν
ν
-
m
+
n
-
3
-
m
-
2
ν
-
2
m
+
4
-
n
-
2
ν
-
2
n
+
4
-
1
-
m
-
2
ν
-
2
m
+
4
-
n
-
2
ν
-
2
n
+
4
-
1
-
m
-
2
ν
-
2
m
+
4
-
n
-
2
ν
-
2
n
+
4
ν
-
m
+
n
-
3
-
m
-
2
ν
-
2
m
+
4
-
n
-
2
ν
-
2
n
+
4
.On performing elementary operations, we finally arrive at(48)νI-QKm∘eKn=ν-m+n-4ν-m-2m-3ν-n-2n-3ν3-3m+3n-10ν2+2m2+n2+4mn-11m-11n+20ν-4m+n-4m-2n-2.On equating to zero and extracting eigenvalues from the equation above, the theorem follows.Corollary 13.
From Lemma7, the energy (adjacency) of line graph of Km∘eKn is given by(49)ELKm∘eKn=m2+n2-3m-3n+2+m+n-6+m-4m-3+n-4n-3+λ1+λ2+λ3,where, λ1, λ2, and λ3 are the roots of the cubic equation:(50)λ3-3m+3n-16λ2+2m2+2n2+8mn-34m-34n+92λ+4m2+n2+4mn-14m-14n+32-m+n-4mn-2m-2n+4=0.Corollary 14.
From Lemma8, the energy (adjacency) of subdivision graph of Km∘eKn where m,n≥2 is given by(51)ESKm∘eKn=2m+n-4+2m-2m-3+2n-2n-3+λ1+λ2+λ3, where λ1, λ2, and λ3 are the roots of the equation(52)λ3-3m+3n-10λ2+2m2+n2+4mn-11m-11n+20λ-4m+n-4m-2n-2=0.



---

*Source: 5906801-2016-10-25.xml*