# Signless Laplacian Polynomial and Characteristic Polynomial of a Graph

Authors: Harishchandra S. Ramane; Shaila B. Gudimani; Sumedha S. Shinde
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

The signless Laplacian polynomial of a graphG is the characteristic polynomial of the matrix Q(G)=D(G)+A(G), where D(G) is the diagonal degree matrix and A(G) is the adjacency matrix of G. In this paper we express the signless Laplacian polynomial in terms of the characteristic polynomial of the induced subgraphs, and, for regular graph, the signless Laplacian polynomial is expressed in terms of the derivatives of the characteristic polynomial. Using this we obtain the characteristic polynomial of line graph and subdivision graph in terms of the characteristic polynomial of induced subgraphs.


---

## Body

## 1. Introduction

LetG be a simple graph with n vertices and m edges. Let the vertex set of G be V(G)={v1,v2,…,vn}. Let degG(v) denote the degree of a vertex v in G. The adjacency matrix of a graph G is A(G)=[aij], where aij=1 if vi is adjacent to vj and aij=0, otherwise. The characteristic polynomial of a graph G is defined as ϕ(G:λ)=det(λI-A(G)), where I is an identity matrix of order n. The degree matrix of a graph G is the diagonal matrix D(G)=diag[d1,d2,…,dn], where di=degG(vi), i=1,2,…,n. The matrix C(G)=D(G)-A(G), is called the Laplacian matrix and the matrix Q(G)=D(G)+A(G) is called the signless Laplacian matrix or Q-matrix of G. The characteristic polynomial of C(G), defined as C(G:λ)=det(λI-C(G)), is called the Laplacian polynomial of G. The characteristic polynomial of Q(G), defined as Q(G:λ)=det(λI-Q(G)), is called the signless Laplacian polynomial or Q-polynomial of a graph G, where I is an identity matrix of order n.Several results on Laplacian ofG are reported in the literature (see, e.g., [1–4]). Recently signless Laplacian attracted the attention of researchers [5–12]. In [13], the Laplacian polynomial of a graph is expressed in terms of the characteristic polynomial of the induced subgraphs. In this paper we express signless Laplacian polynomial of a graph in terms of the characteristic polynomial of its induced subgraphs. Further the signless Laplacian polynomial of a regular graph is expressed in terms of the derivatives of its characteristic polynomial. Using these results, we express characteristic polynomial of line graph and of subdivision graph in terms of the characteristic polynomial of its induced subgraphs.We use standard terminology of graph theory [14].


## 2. Signless Laplacian Polynomial in terms of Characteristic Polynomial

Let the setMk(G)={S∣S⊆V(G)and|S|=k}, k=0,1,2,…,n. Note that |Mk(G)|=(nk). We denote the product of degrees of the vertices of G which belongs to S by PG(S), that is, PG(S)=∏v∈S‍degG(v). The graph G-S is an induced subgraph of G with vertex set V(G)-S. If S=V(G), then G-S=K0, a graph without vertices. Note that ϕ(K0:λ)=1.Theorem 1 (see [15] (kth derivative)).
LetG be a graph with n vertices, then
(1)dkdλkϕ(G:λ)=k!∑S∈Mk(G)ϕ(G-S:λ),0≤k≤n.Theorem 2.
LetG be a graph with n vertices, then
(2)Q(G:λ)=∑k=0n{(-1)k∑S∈Mk(G)(PG(S))ϕ(G-S:λ)}.Proof.
LetA(G)=[aij], 1≤i,j≤n be the adjacency matrix of G and D(G)=diag[d1,d2,…,dn], where di=degG(vi), i=1,2,…,n. Then,
(3)Q(G:λ)=det(λI-Q(G))=det(λI-D(G)-A(G))=|λ-d1-a12-a13⋯-a1n-a21λ-d2-a23⋯-a2n-a31-a32λ-d3⋯-a3n⋮⋮-an1-an2-an3⋯λ-dn|.
Splitting the determinant of (3) as a sum of two determinants, we get
(4)Q(G:λ)=|λ-a12-a13⋯-a1n-a21λ-d2-a23⋯-a2n-a31-a32λ-d3⋯-a3n⋮⋮-an1-an2-an3⋯λ-dn|+|-d100⋯0-a21λ-d2-a23⋯-a2n-a31-a32λ-d3⋯-a3n⋮⋮-an1-an2-an3⋯λ-dn|.
Again splitting each of the determinants of (4) as a sum of two determinants and continuing the procedure in succession, at nth step we get
(5)Q(G:λ)=|λI-A(G)|+∑1≤i≤n(-di)|λI-A(G-vi)|+∑1≤i<j≤n(-di)(-dj)|λI-A(G-vi-vj)|+⋯+∑1≤i<j<⋯<l≤n(-di)(-dj)⋯(-dl)×|λI-A(G-vi-vj-⋯-vl)|.
(in the above expression,I stands for the identity matrix of the appropriate order and G-vi is a vertex deleted subgraph of G) and(6)Q(G:λ)=|λI-A(G)|+(-1)∑S∈M1(G)(PG(S))|λI-A(G-S)|+(-1)2∑S∈M2(G)(PG(S))|λI-A(G-S)|+⋯+(-1)n∑S∈Mn(G)(PG(S))|λI-A(G-S)|=∑k=0n{(-1)k∑S∈Mk(G)(PG(S))|λI-A(G-S)|}=∑k=0n{(-1)k∑S∈Mk(G)(PG(S))ϕ(G-S:λ)}.Corollary 3.
IfG is an r-regular graph with n vertices, then
(7)Q(G:λ)=∑k=0n(-1)krkk!dkdλkϕ(G:λ).Proof.
The graphG is an r-regular graph, therefore PG(S)=rk for all S∈Mk(G). Substituting this in (2) gives that
(8)Q(G:λ)=∑k=0n{(-1)k∑S∈Mk(G)rkϕ(G-S:λ)}=∑k=0n(-1)krk∑S∈Mk(G)ϕ(G-S:λ)=∑k=0n(-1)krkk!dkdλkϕ(G:λ)from(1).


## 3. Characteristic Polynomial of Line Graph and Subdivision Graph

Theline graphL(G) of a graph G is the graph whose vertex set has one-to-one correspondence to the edge set of G and two vertices in L(G) are adjacent if and only if the corresponding edges have a vertex in common in G.Theorem 4.
LetG be a graph with n vertices and m edges and L(G) is the line graph of G, then
(9)ϕ(L(G):λ)=(λ+2)m-n×∑k=0n{(-1)k∑S∈Mk(G)(PG(S))ϕ(G-S:λ+2)}.Proof.
IfG is a graph with n vertices and m edges, then [8]
(10)ϕ(L(G):λ)=(λ+2)m-nQ(G:λ+2).
From (2),
(11)Q(G:λ+2)=∑k=0n‍{(-1)k∑S∈Mk(G)(PG(S))ϕ(G-S:λ+2)}.
Substituting (11) in (10), the result follows.Corollary 5.
IfG is an r-regular graph with n vertices, then
(12)ϕ(L(G):λ)=(λ+2)n(r-2)/2∑k=0n(-1)krkk!dkdxkϕ(G:x)|x=λ+2.Proof.
The graphG is an r-regular graph, therefore PG(S)=rk for all S∈Mk(G) and the number of edges of G is m=nr/2.
Therefore, from (9),
(13)ϕ(L(G):λ)=(λ+2)n(r-2)/2∑k=0n{(-1)k∑S∈Mk(G)rkϕ(G-S:λ+2)}=(λ+2)n(r-2)/2∑k=0n{(-1)krk∑S∈Mk(G)ϕ(G-S:x)}x=λ+2=(λ+2)n(r-2)/2∑k=0n(-1)krkk!×dkdxkϕ(G:x)|x=λ+2from(1).Thesubdivision graphS(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G.Theorem 6.
LetG be a graph with n vertices, m edges and S(G) is the subdivision graph of G, then
(14)ϕ(S(G):λ)=λm-n∑k=0n{(-1)k∑S∈Mk(G)(PG(S))ϕ(G-S:λ2)}.Proof.
IfG is a graph with n vertices and m edges, then [8]
(15)ϕ(S(G):λ)=λm-nQ(G:λ2).
From (2),
(16)Q(G:λ2)=∑k=0n{(-1)k∑S∈Mk(G)(PG(S))ϕ(G-S:λ2)}.
Substituting (16) in (15), the result follows.Corollary 7.
IfG is an r-regular graph with n vertices, then
(17)ϕ(S(G):λ)=λn(r-2)/2∑k=0n(-1)krkk!dkdxkϕ(G:x)|x=λ2.Proof.
AsG is an r-regular graph, PG(S)=rk for all S∈Mk(G) and the number of edges of G is m=nr/2.
Therefore, from (14),
(18)ϕ(S(G):λ)=λn(r-2)/2∑k=0n{(-1)k∑S∈Mk(G)rkϕ(G-S:λ2)}=λn(r-2)/2∑k=0n{(-1)krk∑S∈Mk(G)ϕ(G-S:x)}x=λ2=λn(r-2)/2∑k=0n(-1)krkk!dkdxkϕ(G:x)|x=λ2from(1).


## 4. Number of Spanning Trees

IfG is an r-regular graph, then
(19)Q(G:λ)=|λI-Q(G)|=|λI-D(G)-A(G)|=|(λ-r)I-A(G)|sinceD=rI=ϕ(G:λ-r)which gives that(20)Q(G:2r-λ)=ϕ(G:r-λ).Also for anr-regular graph G [3, 16],
(21)C(G:λ)=(-1)nϕ(G:r-λ).Letτ(G) be the number of spanning trees of G, then [3, 16]
(22)τ(G)=(-1)n-1nddλC(G:λ)|λ=0.Here we give the number of spanning trees using signless Laplacian.Theorem 8.
IfG is an r-regular graph with n vertices, then
(23)τ(G)=1nddλQ(G:λ)|λ=2r.Proof.
From (22),
(24)τ(G)=(-1)n-1nddλC(G:λ)|λ=0=(-1)n-1nddλ(-1)nϕ(G:r-λ)|λ=0from(21),=(-1)n-1nddλ(-1)nQ(G:2r-λ)|λ=0from(20)=(-1)n-1nddλ(-1)n(-1)Q(G:λ)|λ=2r=1nddλQ(G:λ)|λ=2r.


## 5. Conclusion

Equation (2) establishes the relationship between the signless Laplacian polynomial and characteristic polynomial of a graph. Equations (9) and (14) express the characteristic polynomial of line graph and of subdivision graph in terms of the characteristic polynomial of a graph. As corollaries of these results, (12) and (17) give the characteristic polynomial of line graph and the subdivision graph of a regular graph in terms of the derivatives of the characteristic polynomial of a graph. These results are different from those obtained in [17, 18].



---

*Source: 105624-2013-01-03.xml*