Let G be a simple, undirected graph with vertex set V(G)={v1,v2,…,vn}. The degree d_i of a vertex v_i 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 v_i and v_j are adjacent, s_ij = 1 if the vertices v_i and v_j 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]

(1.1)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 d_i denotes the degree of a vertex v_i.

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.

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 d_v being the degree of the vertex v with P_G(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=K₀, a graph without vertices. We take ϕS(K0:λ)=1.

Theorem 2.1.

Let G be a graph on n vertices. Then

(2.1)ϕ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<j≤n(−pi)(−pj)|λI+S(G−vi−vj)|+⋯     +∑1≤i<j<⋯<k≤n(−pi)(−pj)⋯(−pk)|λI+S(G−vi−vj−⋯−vk)|    =(−1)n|−λI−S(G)|+∑M∈N1(G)PG(M)|−λI−S(G−M)|     +∑M∈N2(G)PG(M)|−λI−S(G−M)|+⋯     +∑M∈Nn(G)PG(M)|−λI−S(G−M)|    =(−1)n∑k=0n∑M∈Nk(G)PG(M)|−λI−S(G−M)|    =(−1)n∑k=0n∑M∈Nk(G)PG(M)ϕS(G−M:−λ)

Following Lemma gives the k^th derivative of Seidel polynomial.

Lemma 2.2.

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

(2.2)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

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

where S_i(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

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

where G_i is the graph obtained by removing the i^th 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,

(2.5)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

(2.6)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 G₁ and G₂ be any two graphs. The join of G₁ and G₂ is G1∇G2, obtained by joining each vertex of G₁ to all the vertices of G₂.

Theorem 2.5.

If G₁ is an r₁-regular graph on n₁ vertices and G₂ is an r₂-regular graph on n₂ 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,

(2.7)λ−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 s_ij is the (i,j)-th entry of S(G₁) for i,j=1,2,…,n1 and s'_ij is the (i,j)-th entry of S(G₂) for i,j=1,2,…,n2.

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

(2.8)λ−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 (n₁ + 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,

(2.9)λ−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,

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

where

(2.11)|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,

(2.12)λ−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,

(2.13)(λ+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,

(2.14)|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,

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

Similarly from the Eq. (2.11) we get,

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

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

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

(3.1)ϕ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, p_i=n-1-2d_i 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<j≤n(−pi)(−pj)|λI−S(G−vi−vj)|+⋯   +∑1≤i<j<⋯<k≤n(−pi)(−pj)⋯(−pk)|λI−S(G−vi−vj−⋯−vk)|  =|λI−S(G)|+(−1)∑M∈N1(G)PG(M)|λI−S(G−M)|   +(−1)2∑M∈N2(G)PG(M)|λI−S(G−M)|+⋯   +(−1)n∑M∈Nn(G)PG(M)|λI−S(G−M)|  =∑k=0n(−1)k∑M∈Nk(G)PG(M)|λI−S(G−M)|  =∑k=0n(−1)k∑M∈Nk(G)PG(M)ϕS(G−M:λ).

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 G₁ is an r₁-regular graph on n₁ vertices and G₂ is an r₂-regular graph on n₂ 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,

(3.3)λ−x−s12…−s1n111…1−s21λ−x…−s2n111…1⋮⋮⋱⋮⋮⋮⋱⋮−sn11−sn12…λ−x11…111…1λ−y− s′12…− s′1n211…1− s′21λ−y…− s′2n2⋮⋮⋱⋮⋮⋮⋱⋮11…1− s′n21− s′n22…λ−y, 

where s_ij is the (i,j)-th entry in S(G₁) for i,j=1,2,…,n1 and s'_ij is the (i,j)-th entry in S(G₂) for i,j=1,2,…,n2.

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

 λ−x−s12…−s1n111…1−s21λ−x…−s2n111…1⋮⋮⋱⋮⋮⋮⋱⋮−sn11−sn12…λ−x11…111…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 (n₁ + 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,

(3.4)λ−x−s12…−s1n1n2−s21λ−x…−s2n1n2⋮⋮⋱⋮⋮−sn11−sn12…λ−xn211…1λ+s|B|, 

where

(3.5)|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

(3.6)(λ+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,

(3.7)|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,

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

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