Article Search
eISSN 0454-8124
pISSN 1225-6951

### Article

Kyungpook Mathematical Journal 2021; 61(1): 155-168

Published online March 31, 2021

### On the Seidel Laplacian and Seidel Signless Laplacian Polynomials of Graphs

Harishchandra S. Ramane*, K. Ashoka and Daneshwari Patil, B. Parvathalu

Department of Mathematics, Karnatak University, Dharwad - 580003, India
e-mail : hsramane@yahoo.com, ashokagonal@gmail.com and daneshwarip@gmail.com

Department of Mathematics, Karnatak University's Karnatak Arts College, Dharwad - 580001, India
e-mail : bparvathalu@gmail.com

Received: July 8, 2020; Revised: August 23, 2020; Accepted: October 5, 2020

We express the Seidel Laplacian polynomial and Seidel signless Laplacian polynomial of a graph in terms of the Seidel polynomials of induced subgraphs. Further, we determine the Seidel Laplacian polynomial and Seidel signless Laplacian polynomial of the join of regular graphs.

Keywords: Seidel Laplacian polynomial, Seidel signless Laplacian polynomial, join of graphs.

### 1. Introduction

Let G be a simple, undirected graph with vertex set $V(G)={v1,v2,…,vn}$. The degree di of a vertex vi is the number of edges incident to it. A graph G is said to be an r-regular graph if the degree of each vertex of G is equal to r. If v is a vertex of G, then G-v is a graph obtained from G by removing the vertex v along with the edges incident to v. The Seidel matrix of a graph G is an $n×n$ matrix, defined as, $S(G)=[sij]$, where $sij=−1$ if the vertices vi and vj are adjacent, sij = 1 if the vertices vi and vj are not adjacent and $sij=0$ if i = j. The characteristic polynomial of S(G), denoted by $ϕS(G:λ)$ is called the Seidel polynomial of G [3]. Let $λ1,λ2,…,λn$ be the eigenvalues of S(G).

The collection of the eigenvalues of the Seidel matrix of a graph G is called the Seidel spectrum of G [2].

The Seidel energy SE(G) of a graph G is defined as [6]

$SE(G)=∑ i=1n|λi| .$

The Eq. (1.1) is analogous to an ordinary graph energy defined as the sum of the absolute values of the eigenvalues of adjacency matrix of G [5]. For more details about the graph energy one can refer [8]. Results on Seidel energy can be found in [1, 4, 6, 7, 9, 11, 12, 15].

Let $DS(G)=diag(n−1−2d1,n−1−2d2,…,n−1−2dn)$ be the diagonal matrix in which di denotes the degree of a vertex vi.

The Seidel Laplacian matrix of a graph G is defined as [14]

$SL(G)=DS(G)−S(G)$

and the Seidel signless Laplacian matrix of a graph G is defined as [13]

$SL+(G)=DS(G)+S(G).$

The characteristic polynomial of SL(G) is called the Seidel Laplacian polynomial and is denoted by $ϕSL(G:λ)$. The characteristic polynomial of SL+(G) is called the Seidel signless Laplacian polynomial and is denoted by $ϕSL+(G:λ)$. Results on Seidel Laplacian eigenvalues and Seidel signless Laplacian eigenvalues can be found in [13, 14]. In [10, 16] the expression for the Laplacian polynomial and signless Laplacian polynomial of a graph in terms of the characteristic polynomial of induced subgraphs is given. In this paper we obtain the Seidel Laplacian polynomial and the Seidel signless Laplacian polynomial of a graph in terms of the Seidel polynomial of the induced subgraphs of G. Using these results we express the Seidel Laplacian polynomial and the Seidel signless Laplacian polynomial of regular graphs in terms of the derivatives of the Seidel polynomial. Further we obtain the Seidel Laplacian polynomial and Seidel signless Laplacian polynomial of the join of regular graphs.

### 2. Seidel Laplacian Polynomial

Let the set $Nk(G)={M∣M⊆V(G) and |M|=k}$, $k=0,1,2,…,n$. Note that $|Nk(G)|=n k$. Let $PG(M)=∏ v∈M(n−1−2dv)$, where dv being the degree of the vertex v with PG(M) = 1 for k=0. Let the graph G-M be an induced subgraph of G with the vertex set V(G)-M. If M=V(G), then G-M=K0, a graph without vertices. We take $ϕS(K0:λ)=1$.

### Theorem 2.1.

Let G be a graph on n vertices. Then

$ϕSL(G:λ)=(−1)n∑ k=0 n∑ M∈Nk(G) PG(M) ϕS(G−M:−λ).$

Proof. Let I be an identity matrix.

$ϕSL(G:λ)=|λI−SL(G)| =|λI−DS(G)+S(G)| = λ−(n−1−2d1 ) s12 ⋯ s1n s21 λ−(n−1−2d2 ) ⋯ s2n ⋮ ⋮ ⋱ ⋮ sn1 sn2 ⋯ λ−(n−1−2dn ) = λ−p1 s12 ⋯ s1n s21 λ−p2 ⋯ s2n ⋮ ⋮ ⋱ ⋮ sn1 sn2 ⋯ λ−pn ,$

where $pi=n−1−2di$, $i=1,2,…,n$.

Splitting the above determinant as the sum of two determinants, we get

$ϕSL(G:λ)=λs12⋯s1ns21λ−p2⋯s2n⋮⋮⋱⋮sn1sn2⋯λ−pn+−p10⋯0s21λ−p2⋯s2n⋮⋮⋱⋮sn1sn2⋯λ−pn.$

Again splitting each of the above determinants as the sum of two determinants and continuing the same procedure in succession, at the n-th step we have,

$ϕSL(G:λ)=|λI+S(G)|+∑1≤i≤n(−pi)|λI+S(G−vi)| +∑1≤i

Following Lemma gives the kth derivative of Seidel polynomial.

### Lemma 2.2.

Let G be a graph with n vertices and $0≤k≤n$. Then

$dkdλkϕS(G:λ)=k!∑ M∈N k (G)ϕS(G−M:λ).$

Proof. We prove this by induction. The result is obvious for k = 0. Now for k = 1, we have

$ddλϕS(G:λ)=ddλ|λIn−S(G)|=∑ i=1 n|λIn−1−Si(G)|,$

where Si(G) is the matrix obtained by eliminating i-th row and i-th column from S(G). The Eq. (2.3) can be written as

$ddλϕS(G:λ)=∑ i=1nϕS(Gi:λ),$

where Gi is the graph obtained by removing the ith vertex of G, $i=1,2,…,n$. The Eq. (2.4) can be written as

$ddλϕS(G:λ)=∑ i=1nϕS(G−vi:λ) =∑ M∈N1 (G)ϕS(G−M:λ).$

Assume that the result is true for (k-1)-th derivative. That is,

$dk−1dλk−1ϕS(G:λ)=(k−1)!∑ M′ ∈N k−1 (G)ϕS(G−M′:λ).$

Clearly, G-M' is the graph with n-k+1 vertices. Now differentiating the Eq. (2.5) with respect to $λ$, we have

$dkdλkϕS(G:λ)=(k−1)! ddλ∑ M′ ∈N k−1 (G)ϕS(G−M′:λ) =(k−1)!∑ M′ ∈N k−1 (G)ddλϕS(G−M′:λ) =(k−1)!∑ M′ ∈N k−1 (G)∑ v∈V(G−M′ )ϕS(G−M′−v:λ).$

In Eq. (2.6), the inside summation is taken $n−k+11$ times and the outside summation is taken $nk−1$ times. Therefore, the Eq. (2.6) reduces to,

$dkdλkϕS(G:λ)=k(k−1)!∑ M′ ∪{v}∈N k (G)ϕS(G−(M′∪{v}):λ) =k!∑ M∈N k (G)ϕS(G−M:λ) (since M=M′∪{v}).$

### Corollary 2.3.

If G is an r-regular graph with n vertices, then

$ϕSL(G:λ)=(−1)n∑ k=0 n(n−2r−1)kk!dkdxkϕS(G:x)∣x=−λ.$

Proof. For an r-regular graph G, $PG(M)=(n−2r−1)k$, if $M∈Nk(G)$. Thus, the result follows from the Eqs. (2.1) and (2.2).

### Definition 2.4.

Let G1 and G2 be any two graphs. The join of G1 and G2 is $G1∇G2$, obtained by joining each vertex of G1 to all the vertices of G2.

### Theorem 2.5.

If G1 is an r1-regular graph on n1 vertices and G2 is an r2-regular graph on n2 vertices, then

$ϕSL(G1∇G2:λ)=[(λ+n1)(λ+n2)−n1n2](λ+n1)(λ+n2)ϕSL(G1:λ+n2)ϕSL(G2:λ+n1).$

Proof. We have, $ϕ(SL(G1∇G2):λ)$

$=|λI−SL(G1∇G2)|= (λ−(n1 −n2 −2r1 −1))In1 +S(G1 ) −Jn1 ×n2 −Jn2 ×n1 (λ−(n2 −n1 −2r2 −1))In2 +S(G2 ) = (λ−x)In1 +S(G1 ) −Jn1 ×n2 −Jn2 ×n1 (λ−y)In2 +S(G2 ) ,$

where J is the matrix with all entries equal to one, $x=n1−n2−2r1−1$ and $y=n2−n1−2r2−1$. The above determinant can be re-written as,

$λ−xs12…s1n1−1−1…−1s21λ−x…s2n1−1−1…−1⋮⋮⋱⋮⋮⋮⋱⋮sn11sn12…λ−x−1−1…−1−1−1…−1λ−y s′12… s′1n2−1−1…−1 s′21λ−y… s′2n2⋮⋮⋱⋮⋮⋮⋱⋮−1−1…−1 s′n21 s′n22…λ−y,$

where sij is the (i,j)-th entry of S(G1) for $i,j=1,2,…,n1$ and s'ij is the (i,j)-th entry of S(G2) for $i,j=1,2,…,n2$.

Performing row and column transformations on the determinant (2.7) which leave its value unchanged. Subtracting (n1+1)-th row from the rows $(n1+2),(n1+3),…,(n1+n2)$, we have

$λ−xs12…s1n1−1−1…−1s21λ−x…s2n1−1−1…−1⋮⋮⋱⋮⋮⋮⋱⋮sn11sn12…λ−x−1−1…−1−1−1…−1λ−y s′12… s′1n200…0 s′21−λ+yλ−y− s′12… s′2n2− s′1n2⋮⋮⋱⋮⋮⋮⋱⋮00…0 s′n21−λ+y s′n22− s′12…λ−y− s′1n2.$

Adding the columns $(n1+2),(n1+3),…,(n1+n2)$ to the column (n1 + 1) in (2.8) and taking into account

$∑ j=1 n1sij=n1−1−2r1 for i=1,2,…,n1$

and

$∑ j=1 n2s′ij=n2−1−2r2 for i=1,2,…,n2,$

we get,

$λ−xs12…s1n1−n2−1…−1s21λ−x…s2n1−n2−1…−1⋮⋮⋱⋮⋮⋮⋱⋮sn11sn12…λ−x−n2−1…−1−1−1…−1λ+n1 s′12… s′1n200…00λ−y− s′12… s′2n2− s′1n2⋮⋮⋱⋮⋮⋮⋱⋮00…00 s′n22− s′12…λ−y− s′1n2.$

The determinant (2.9) can be written as,

$λ−xs12…s1n1−n2s21λ−x…s2n1−n2⋮⋮⋱⋮⋮sn11sn12…λ−x−n2−1−1…−1λ+n1|B|,$

where

$|B|=λ−y−s′12s′23−s′13…s′2n2−s′1n2s′32−s′12λ−y−s′13…s′3n2−s′1n2⋮⋮⋱⋮s′n22−s′12s′n23−s′13…λ−y−s′1n2.$

Subtracting the row 1 from the rows $2,3,…,n1$ in the first determinant of (2.10) we get,

$λ−xs12…s1n1−n2s21−λ+xλ−x−s12…s2n1−s1n10⋮⋮⋱⋮⋮sn11−λ+xsn12−s12…λ−x−s1n10−1−1…−1λ+n1|B|.$

Adding columns $2,3,…,n1$ to the column 1 of the Eq. (2.12) we get

$λ+n2s12…s1n1−n20λ−x−s12…s2n1−s1n10⋮⋮⋱⋮⋮0sn12−s12…λ−x−s1n10−n1−1…−1λ+n1|B|.$

Expanding the first determinant along the first column we get,

$(λ+n1)(λ+n2)|A|+(−1)n1+2(−n1)(−1)n1+1(−n2)|A||B|.$

That is,

$(λ+n1)(λ+n2)−n1n2|A| |B|,$

where

$|A|=λ−x−s12s23−s13…s2n1−s1n1s32−s12λ−x−s13…s3n1−s1n1⋮⋮⋱⋮sn12−s12sn13−s13…λ−x−s1n1.$

The above determinant can be written as,

$|A|=1(λ+n2)λ+n2s12s13…s1n10λ−x−s12s23−s13…s2n1−s1n10s32−s12λ−x−s13…s3n1−s1n1⋮⋮⋮⋱⋮0sn12−s12sn13−s13…λ−x−s1n1.$

Subtracting the columns $2,3,…,n1$ of (2.14) from the column 1, we obtain

$|A|=1(λ+n2)λ+n2−(n1−2r1−1)s12s13…s1n1−λ+x+s21λ−x−s12s23−s13…s2n1−s1n1−λ+x+s31s32−s12λ−x−s13…s3n1−s1n1⋮⋮⋮⋱⋮−λ+x−sn11sn12−s12sn13−s13…λ−x−s1n1.$

Adding the row 1 to the rows $2,3,…,n1$ we have,

$|A|=1(λ+n2)λ+n2−(n1−2r1−1)s12…s1n1s21λ+n2−(n1−2r1−1)…s2n1s31s32…s3n1⋮⋮⋱⋮sn11sn12…λ+n2−(n1−2r1−1).$

That is,

$|A|=1(λ+n2)|(λ+n2)I−SL(G1)| =1(λ+n2)ϕSL(G1:λ+n2).$

Similarly from the Eq. (2.11) we get,

$|B|=1(λ+n1)ϕSL(G2:λ+n1).$

Thus, the result follows from the Eqs. (2.13), (2.15) and (2.16).

### 3. Seidel Signless Laplacian Polynomial

In this section we use analogous techniques of Section 2 to obtain the Seidel signless Laplacian polynomial.

### Theorem 3.1.

Let G be a graph on n vertices. Then

$ϕSL+(G:λ)=∑ k=0n (−1)k ∑ M∈N k(G) PG(M) ϕS(G−M:λ).$

Proof. We have $SL+(G)=DS(G)+S(G)$. Therefore

$ϕSL+(G:λ)=|λI−SL+(G)| =|λI−DS(G)−S(G)| = λ−(n−1−2d1 ) −s12 ⋯ −s1n −s21 λ−(n−1−2d2 ) ⋯ −s2n ⋮ ⋮ ⋱ ⋮ −sn1 −sn2 ⋯ λ−(n−1−2dn ) = λ−p1 −s12 ⋯ −s1n −s21 λ−p2 ⋯ −s2n ⋮ ⋮ ⋱ ⋮ −sn1 −sn2 ⋯ λ−pn ,$

where, pi=n-1-2di for $i=1,2,…,n$.

Splitting the above determinant as sum of two determinants, we have

$ϕSL+(G:λ)=λ−s12⋯−s1n−s21λ−p2⋯−s2n⋮⋮⋱⋮−sn1−sn2⋯λ−pn+−p10⋯0−s21λ−p2⋯−s2n⋮⋮⋱⋮−sn1−sn2⋯λ−pn.$

Again splitting each of the above determinants as sum of two determinants and continuing the same procedure in succession, at the n-th step we have,

$ϕSL+(G:λ)=|λI−S(G)|+∑1≤i≤n(−pi)|λI−S(G−vi)| +∑1≤i

### Corollary 3.2.

If G is an r-regular graph with n vertices, then

$ϕSL+(G:λ)=∑ k=0n(−1)k(n−2r−1)kk!dkdλkϕS(G:λ).$

Proof. For an r-regular graph, $PG(M)=(n−2r−1)k$ if $M∈Nk(G)$. Thus, the result follows from Eqs. (3.1) and (2.2).

### Theorem 3.3.

If G1 is an r1-regular graph on n1 vertices and G2 is an r2-regular graph on n2 vertices, then

$ϕSL+(G1∇G2:λ)=[(λ+s)(λ+t)−n1n2](λ+s)(λ+t)ϕSL+(G1:λ+n2)ϕSL+(G2:λ+n1),$

where $s=n1−(2n2−4r2−2)$ and $t=n2−(2n1−4r1−2)$.

Proof. We have,

$ϕSL+(G1∇G2:λ)=|λI−SL+(G1∇G2)| = (λ−x)In1 −S(G1 ) Jn1 ×n2 Jn2 ×n1 (λ−y)In2 −S(G2 ) ,$

where J is the matrix with all entries equal to 1, $x=n1−n2−2r1−1$ and $y=n2−n1−2r2−1$.

The above determinant can be written as,

where sij is the (i,j)-th entry in S(G1) for $i,j=1,2,…,n1$ and s'ij is the (i,j)-th entry in S(G2) for $i,j=1,2,…,n2$.

Performing row and column transformations on the determinant (3.3) which leave its value unchanged. Subtracting row (n1+1) from the rows $(n1+2),(n1+3),…,(n1+n2)$ in (3.3) we have,

Adding the columns $(n1+2),(n1+3),…,(n1+n2)$ to the column (n1 + 1) and using

$∑ j=1 n1sij=n1−1−2r1 for i=1,2,…,n1$

and

$∑ j=1 n2s′ij=n2−1−2r2 for i=1,2,…,n2$

we get,

$λ−x−s12…−s1n1n21…1−s21λ−x…−s2n1n21…1⋮⋮⋱⋮⋮⋮⋱⋮−sn11−sn12…λ−xn21…111…1λ+s− s′12…− s′1n200…00λ−y+ s′12…− s′2n2+ s′1n2⋮⋮⋱⋮⋮⋮⋱⋮00…00− s′n22+ s′12…λ−y+ s′1n2.$

The above determinant can be written as,

where

$|B|=λ−y+s′12−s′23+s′13…−s′2n2+s′1n2−s′32+s′12λ−y+s′13…−s′3n2+s′1n2⋮⋮⋱⋮−s′n22+s′12−s′n23+s′13…λ−y+s′1n2.$

Subtracting the row 1 from the rows $2,3,…,n1$ of (3.4) we get,

$λ−x−s12…−s1n1n2−s21−λ+xλ−x+s12…−s2n1+s1n10⋮⋮⋱⋮⋮−sn11−λ+x−sn12+s12…λ−x+s1n1011…1λ+s|B|.$

Adding the columns $2,3,…,n1$ to the column 1, we have

$λ+t−s12…−s1n1n20λ−x+s12…−s2n1+s1n10⋮⋮⋱⋮⋮0−sn12+s12…λ−x+s1n10n11…1λ+s|B|.$

Expanding the first determinant along the first column we get

$(λ+t)(λ+s)−n1n2|A||B|,$

where

$|A|=λ−x+s12−s23+s13…−s2n1+s1n1−s32+s12λ−x+s13…−s3n1+s1n1⋮⋮⋱⋮−sn12+s12−sn13+s13…λ−x+s1n1.$

The above determinant can be written as,

$|A|=1λ+tλ+t−s12−s13…−s1n10λ−x+s12−s23+s13…−s2n1+s1n10−s32+s12λ−x+s13…−s3n1+s1n1⋮⋮⋮⋱⋮0−sn12+s12−sn13+s13…λ−x+s1n1.$

Subtracting the columns $2,3,…,n1$ from the column 1, we get

$A|=1λ+tλ−x−s12−s13…−s1n1−λ+x−s21λ−x+s12−s23+s13…−s2n1+s1n1−λ+x−s31−s32+s12λ−x+s13…−s3n1+s1n1⋮⋮⋮⋱⋮−λ+x−sn11−sn12+s12−sn13+s13…λ−x+s1n1.$

Adding the row 1 to rows $2,3,…,n1$ we have,

$|A|=1λ+t λ−x −s12 ⋯ −s1n1 −s21 λ−x ⋯ −s2n1 −s31 −s32 … −s3n1 ⋮ ⋮ ⋱ ⋮ sn11 sn12 ⋯ λ−x =1λ+t|(λ+n2)I−SL+(G1)| =1λ+tϕSL+(G1:λ+n2).$

Similarly we get,

$|B|=1λ+sϕSL+(G2:λ+n1).$

The result follows by substituting the Eqs. (3.7) and (3.8) in Eq. (3.6).

### Acknowledgements.

H. S. Ramane thanks the University Grants Commission (UGC), New Delhi for support through grant under UGC-SAP DRS-III Programme: F.510/3/ DRS-III/2016 (SAP-I). K. Ashoka thanks the Karnatak University for URS fellowship No. URS/2019-344. D. Patil thanks Karnataka Science and Technology Promotion Society, Bengaluru for fellowship No. DST/KSTePS/Ph.D Fellowship/OTH-01:2018-19.

1. S. Akbari, M. Einollahzadeh, M. M. Karkhaneei, and M. A. Nematollahi. Nematollahi, Proof of a conjecture on the Seidel energy of graphs, European J. Combin. 86 (2020), 103078. 8 pp.
2. A. E. Brouwer and W. H. Haemers, Haemers, Spectra of graphs, Springer, Berlin, 2012.
3. D. Cvetković, M. Doob, and H. Sachs, Sachs, Spectra of graphs: theory and application, Academic Press, New York, 1980.
4. E. Ghorbani. On eigenvalues of Seidel matrices and Haemers conjecture, Des. Codes Cryptogr. 84(1-2) (2017), 189-195.
5. I. Gutman. The energy of a graph, Ber. Math. Stat. Sekt. Forschungsz. Graz 103 (1978), 1-22.
6. W. H. Haemers. Seidel switching and graph energy, MATCH Commun. Math. Comput. Chem. 68(3) (2012), 653-659.
7. P. Nageswari and P. B. Sarasija. Seidel energy and its bounds, Int. J. Math. Anal. 8(57) (2014), 2869-2871.
8. X. Li, Y. Shi, and I. Gutman, Gutman, Graph energy, Springer, New York, 2012.
9. M. R. Oboudi. Energy and Seidel energy of graphs, MATCH Commun. Math. Comput. Chem. 75(2) (2016), 291-303.
10. H. S. Ramane, S. B. Gudimani, and S. S. Shinde. Signless Laplacian polynomial and characteristic polynomial of a graph, J. Discr. Math. (2013). Art. ID 105624, 4 pp.
11. H. S. Ramane, M. M. Gundloor, and S. M. Hosamani. Seidel equienergetic graphs, Bull. Math. Sci. Appl. 16 (2016), 62-69.
12. H. S. Ramane, I. Gutman, and M. M. Gundloor. Seidel energy of iterated line graphs of regular graphs, Kragujevac J. Math. 39(1) (2015), 7-12.
13. H. S. Ramane, I. Gutman, J. B. Patil, and R. B. Jummannaver. Seidel signless Lapla-cian energy of graphs, Math. Interdisc. Res. 2 (2017), 181-191.
14. H. S. Ramane, R. B. Jummannaver, and I. Gutman. Seidel Laplacian energy of graphs, Int. J. Appl. Graph Theory 1(2) (2017), 74-82.
15. S. K. Vaidya and K. M. Popat. Some new results on Seidel equienergetic graphs, Kyungpook Math. J. 59(2) (2019), 335-340.
16. H. B. Walikar and H. S. Ramane. Laplacian polynomial and number of spanning trees in terms of characteristic polynomial of induced subgraphs, AKCE Int. J. Graphs Combin. 5(1) (2008), 47-55.