검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

KYUNGPOOK Math. J. 2019; 59(2): 335-340

Published online June 23, 2019

Copyright © Kyungpook Mathematical Journal.

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

Received: March 30, 2018; Revised: April 27, 2019; Accepted: May 10, 2019

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.

For standard terminology and notations related to graph theory we follow Balakrishnan and Ranganathan [2] while for any undefined term in algebra we follow Lang [10]. 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 [5] in 1978. A brief account on energy of graph can be found in Cvetkovi [4] and Li [13].

The other varients of energy like Laplacian energy [7], Incidence energy [6], Skew energy [1], Distance energy [3], Seidel energy [8] 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 [8] 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. [11] 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. [12] 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.

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

AB=[a11Ba1nBam1BamnB]

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.([9])

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)=JA

and

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

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(BA)=-2(BA)-II+JJ

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

S(JA)+II=-2(JA)+JJ=J(-2A+J)=J(S(A)+I).

Lemma 2.3

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

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

Much like above,

[S(J(A+I)-II]+I=[-2(J(A+I)-II+JJ-II]+II=J(-2(A+I))+JJ=J(-2(A+I)+J)=J(S(A)-I).

Theorem 2.4

Let G be a graph with Seidel eigenvalues σ1, σ2, · · ·, σn withσim-1m, for all 1 ≤ in then, Dm(G) andDm*(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

imσi+(m-1)=imσ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))andDm(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

im2σi+(m-1)2=im2σ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.

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.

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

  1. C. Adiga, R. Balakrishnan, and W. So. The skew energy of a digraph. Linear Algebra Appl., 432(2010), 1825-1835.
    CrossRef
  2. R. Balakrishnan, and K. Ranganathan. A textbook of graph theory, , Springer-Verlag, New York, 2000.
    CrossRef
  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.
    CrossRef
  7. I. Gutman, and B. Zhou. Laplacian energy of a graph. Linear Algebra Appl., 414(2006), 29-37.
    CrossRef
  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.
    CrossRef
  10. S. Lang. Algebra, , Springer-Verlag, New York, 2002.
    CrossRef
  11. HS. Ramane, MM. Gundloor, and SM. Hosamani. Seidel equienergetic graphs. Bulletin of Mathematical Sciences and Applications., 16(2016), 62-69.
    CrossRef
  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.
    CrossRef
  13. X. Li, Y. Shi, and I. Gutman. Graph energy, , Springer, New York, 2012.
    CrossRef