KYUNGPOOK Math. J. 2019; 59(2): 335-340
Some New Results on Seidel Equienergetic Graphs
Samir K. Vaidya, Kalpesh M. Popat
Department of Mathematics, Saurashtra University, Rajkot-360005, Gujarat, India
e-mail : samirkvaidya@yahoo.co.in

Department of Master of Computer Application, Atmiya Institute Of Technology & Science, Rajkot-360005, Gujarat, India
e-mail : kalpeshmpopat@gmail.com
* Corresponding Author.
Received: March 30, 2018; Revised: April 27, 2019; Accepted: May 10, 2019; Published online: June 23, 2019.

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

The energy of a graph G is the sum of the absolute values of the eigenvalues of the adjacency matrix of G. Some variants of energy can also be found in the literature, in which the energy is defined for the Laplacian matrix, Distance matrix, Common-neighbourhood matrix or Seidel matrix. The Seidel matrix of the graph G is the square matrix in which ijth entry is −1 or 1, if the vertices vi and vj are adjacent or non-adjacent respectively, and is 0, if vi = vj. The Seidel energy of G is the sum of the absolute values of the eigenvalues of its Seidel matrix. We present here some families of pairs of graphs whose Seidel matrices have different eigenvalues, but who have the same Seidel energies.

1. Introduction

For standard terminology and notations related to graph theory we follow Balakrishnan and Ranganathan  while for any undefined term in algebra we follow Lang . Let G be a simple graph with vertex set {v1, v2, · · ·, vn}. The adjacency matrix denoted by A(G) of G is defined to be A(G) = [aij ], such that, aij = 1 if vi is adjacent with vj, and 0 otherwise.

The eigenvalues of A are called the eigenvalues of G. The energy E(G) of graph G is the sum of all absolute values of eigenvalues of G. The concept of energy of graph was introduced by Gutman  in 1978. A brief account on energy of graph can be found in Cvetkovi  and Li .

The other varients of energy like Laplacian energy , Incidence energy , Skew energy , Distance energy , Seidel energy  are also available in the literature. In the present paper we have focused on Seidel energy of graphs.

Let G be a simple graph with vertex set {v1, v2, · · ·, vn}. The Seidel matrix of G which is denoted by S(G) = [sij] is a n × n matrix in which s11 = s22 = · · · = snn = 0, and in which for ij we have sij = −1 if vi is adjacent to vj and sij = 1 otherwise.

The eigenvalues of the Seidel matrix, labeled as σ1, σ2, · · ·, σn, are said to be the Seidel eigenvalues of G. The collection of Seidel eigenvalues together with their multiplicities is known as Seidel spectrum of G denoted by Specs(G). Haemers  has defined the Seidel energy of G as

$SE(G)=∑i=1n∣σi∣$

As an example the, Seidel matrix of the complete graph Kn is IJ. Thus

$Specs(Kn)={1n-1,(1-n)1}$

where a power denotes the multiplicity of an eigenvalue. Therefore, SE(Kn) = 2n − 2.

Two graphs G1 and G2 are said to be Seidel equienergetic if SE(G1) = SE(G2). Of course, Seidel cospectral graphs are Seidel equienergetic. We are interested in graphs which are of same order, non co-spectral and equienergetic in the context of Seidel energy. Let be the complement of the graph G then S(G) = A(G)−A() implying S() = −S(G). Consequently, G and are obviously Seidel equienergetic.

The join of two graphs G1 and G2, denoted by G1+G2, is a graph obtained from G1G2 by joining each vertex of G1 to all vertices of G2. Ramane et al.  proved that if H1 and H2 are Seidel non cospectral, Seidel equienergetic regular graphs on n vertices and of same degree, then for any regular graph G, SE(H1 + G) = SE(H2 + G).

Ramane et al.  also proved that if G1 and G2 are two Seidel non-cospectral r-regular graphs of the same order and of the same degree r ≥ 3, then for any k ≥ 2, the iterated line graphs Lk(G1) and Lk(G2) are Seidel non-cospectral, Seidel equienergetic graphs.

2. Seidel Equienergetic Graphs

To state our results we need to defined some graphs. The categorical product G × H of two graphs G and H is the graph with vertex set V (G) × V (H) in which two vertices (u1, v1) and (u2, v2) are adjacent if u1u2E(G) and v1v2E(H).

Let ARm×n, BRp×q. The Kronecker product (or tensor product) of A and B is defined as the matrix

$A⊗B=[a11B⋯a1nB⋮⋱⋮am1B⋯amnB]$

It is well known and easy to show that for graphs G1 and G2 for which loops are allowed, we have

$A(G1×G2)=A(G1)⊗A(G2)$

The following is useful for determining the spectrum of a product of graphs from those of its factors.

### Proposition 2.1.()

Let AMm and BMn. Furthermore, let σ be eigenvalue of matrix A with corresponding eigenvector x and μ be eigenvalue of matrix B with corresponding eigenvector y. Then σμ is an eigenvalue of AB with corresponding eigenvector xy.

Let Gr be the graph obtained from G by adding loops on every vertex and Gur be the graph obtained from G by removing all loops. For any simple graph G, if we take $G1=Kmr$ and G2 = G, using the facts that A(Gr) = A(G) + I, A(Gur) = A(G) − I,$A(Kmr)=J$ and writing A for A(G), we have,

$A(Kmr×G)=J⊗A$

and

$A(Kmr×Gr)ur=J⊗(A+I)-I⊗I$

We introduce two convenient notations. Let $Dm(G)=Kmr×G$ and $Dm*(G)=(Kmr×Gr)ur$. It is easy to verify that if G is a graph with n vertices then both Dm(G) and $Dm*(G)$ are graphs with mn vertices. The graphs D2(C5) and $D2*(C5)$ are shown in Figure 1.

### Lemma 2.2

If the Seidel spectrum of G is {σ1, σ2, · · ·, σn}then the Seidel spectrum of Dm(G) is

$Specs(Dm(G))={mσi+(m-1)∣i=1,2,⋯,n}∪{-1mn-n}$
Proof

As $A(Kmr)=J=Jm$ has spectrum {m, 0m−1}, we have by Proposition 2.1 that an eigenvalue σi of S(G) yields in $A(Kmr)×(S(G)+I)-I$ an eigenvalue m(σi + 1) − 1 = i + (m − 1) and mnn eigenvalue 0(σi + 1) − 1 = −1. It is enough to show that $S(Kmr×G)=A(Kmr)×(S(G)+I)-I$. Writing A for A(G) and S(M) = −2MI + J for any matrix M, We have to show that S(JA) = J ⊗ (S(A) + I) − I. Observe that first,

$S(B⊗A)=-2(B⊗A)-I⊗I+J⊗J$

and so taking B = J and moving I × I to the other side, $S(Kmr×G)+I$ is

$S(J⊗A)+I⊗I=-2(J⊗A)+J⊗J=J⊗(-2A+J)=J⊗(S(A)+I).$

### Lemma 2.3

If the Seidel spectrum of G is {σ1, σ2, · · ·, σn} then the Seidel spectrum of$Dm*(G)$is

$Specs(Dm*(G))={mσi-(m-1)∣i=1,2,⋯,n}∪{1mn-m}$
Proof

Much like above,

$[S(J⊗(A+I)-I⊗I]+I=[-2(J⊗(A+I)-I⊗I+J⊗J-I⊗I]+I⊗I=J⊗(-2(A+I))+J⊗J=J⊗(-2(A+I)+J)=J⊗(S(A)-I).$

### Theorem 2.4

Let G be a graph with Seidel eigenvalues σ1, σ2, · · ·, σn with$∣σi∣≥m-1m$, for all 1 ≤ in then, Dm(G) and$Dm*(G)$are Seidel non co-spectral equienergetic graphs if and only if G have equal numbers of positive and negative Seidel eigenvalues.

Proof

It is not hard to see that the sums of the spectrums in these two lemma are the same. To say the same about the sums of the absolute values, (so that the Seidel energies are the same) we observe that we need that

$∑i∣mσi+(m-1)∣=∑i∣mσi-(m-1)∣$

Assuming that $∣σi∣>m-1m$, we get that |i + (m − 1) | − |i − (m − 1)| is 2(m − 1) if σi is positive and −2(m − 1) if σi is negative for each i = 1, 2, · · ·, n. It follows that with these restrictions on the eigenvalues that the Seidel energies of Dm(G) and $Dm*(G)$ are the same if and only if G has the same number of positive and negative eigenvalues. This gives Theorem 2.4.

Observe that if G is a graph with n vertices then both $Dm(Dm*(G))$ and $Dm*(Dm(G))$ are graphs with m2n vertices. We next prove following theorem for Seidel equienergetic graphs.

### Theorem 2.5

Let G be a graph with Seidel eigenvalues σ1, σ2, · · ·, σn with$∣σi∣≥(m-1m)2$, for all 1 ≤ in then, $Dm*(Dm(G))$and$Dm(Dm*(G))$are Seidel non co-spectral equienergetic graphs if and only if G has equal numbers of positive and negative Seidel eigenvalues.

Proof

By Lemma 2.2, Dm(G) has spectrum {i + (m − 1) |i = 1, 2, · · ·, n}∪{−1mnn}and by Lemma 2.3 spectrum of $Dm*(Dm(G))$ is {m2σi + (m − 1)2 |i = 1, 2, · · ·, n}∪{(1−2m)mnn}∪{1m2nmn} and again by Lemma 2.2 and Lemma 2.3, spectrum of $Dm(Dm*(G))$ is {m2σi −(m − 1)2 |i = 1, 2, · · ·, n} ∪ {(2m−1)mnn}∪ {−1m2nmn}. To prove $Dm*(Dm(G))$ and $Dm(Dm*(G))$ are equienergetic, it is enough to prove

$∑i∣m2σi+(m-1)2∣=∑i∣m2σi-(m-1)2∣.$

If $∣σi∣>(m-1)2m2$, we have |m2σi + (m + 1)2| − |m2σi − (m − 1)2| is 2(m − 1)2 if σi is positive and −2(m − 1)2 if σi is negative. It follows that $Dm*(Dm(G))$ and $Dm(Dm*(G))$ are Seidel equienergetic if and only if G has equal numbers of positive and negative Seidel eigenvalues.

3. Concluding Remarks

The concept of Seidel equienergetic graphs is analogous to the concepts of equienergetic graphs. We present here methods to construct Seidel equienergetic graphs by means of Gr and Gur from a given graph G.

Acknowledgements

The authors are highly thankful to the anonymous referee for kind suggestions and comments on the first draft of this paper.

Figures Fig. 1. The graphs D2(C5) and $D2*(C5)$
References
1. C. Adiga, R. Balakrishnan, and W. So. The skew energy of a digraph. Linear Algebra Appl., 432(2010), 1825-1835.
2. R. Balakrishnan, and K. Ranganathan. A textbook of graph theory, , Springer-Verlag, New York, 2000.
3. SB. Bozkurt, AD. Gungor, and B. Zhou. Note on distance energy of graphs. MATCH Commun Math Comput Chem., 64(2010), 129-134.
4. D. Cvetkovic̀, P. Rowlison, and S. Simic̀. An introduction to the theory of graph spectra, , Cambridge university press, Cambridge, 2010.
5. I. Gutman. The energy of a graph. Ber Math Statist Sekt Forsch Graz., 103(1978), 1-22.
6. I. Gutman, D. Kiani, M. Mirazakhah, and B. Zhou. On incidence energy of a graph. Linear Algebra Appl., 431(2009), 1223-1233.
7. I. Gutman, and B. Zhou. Laplacian energy of a graph. Linear Algebra Appl., 414(2006), 29-37.
8. WH. Haemers. Seidel switching and graph energy. MATCH Commun Math Comput Chem., 68(2012), 653-659.
9. RA. Horn, and CR. Johnson. Topics In matrix analysis, , Cambridge University Press, Cambridge, 1991.
10. S. Lang. Algebra, , Springer-Verlag, New York, 2002.
11. HS. Ramane, MM. Gundloor, and SM. Hosamani. Seidel equienergetic graphs. Bulletin of Mathematical Sciences and Applications., 16(2016), 62-69.
12. HS. Ramane, I. Gutman, and MM. Gundloor. Seidel energy of iterated line graphs of regular graphs. Kragujevac J Math., 39(1)(2015), 7-12.
13. X. Li, Y. Shi, and I. Gutman. Graph energy, , Springer, New York, 2012. 