• No results found

A Note on Energy of Some Graphs

N/A
N/A
Protected

Academic year: 2023

Share "A Note on Energy of Some Graphs"

Copied!
6
0
0

Loading.... (view fulltext now)

Full text

(1)

A note on energy of some graphs

G. Indulal

Department of Mathematics, St.Aloysius College Edathua, Alappuzha - 689693, India

and

A. Vijayakumar

Department of Mathematics, Cochin University of Science and Technology, Cochin-682 022, India.

Abstract

Eigenvalue of a graph is the eigenvalue of its adjacency matrix. The energy of a graph is the sum of the absolute values of its eigenvalues. In this note we obtain analytic expressions for the energy of two classes of regular graphs.

1 Introduction

LetGbe a graph with |V(G)|=pand an adjacency matrixA. The eigenvalues of A are called the eigenvalues of Gand form the spectrum of Gdenoted by spec(G) [3]. The energy [6] of G,E(G) is the sum of the absolute values of its eigenvalues.

From the pioneering work of Coulson [2] there exists a continuous interest towards the general mathematical properties of the totalπ-electron energyE as calculated within the framework of the H¨uckel Molecular Orbital (HMO) model [7]. These efforts enabled one to get an insight into the dependence ofE on molecular structure. The properties ofE(G) are discussed in detail in [6, 8, 9].

In [5] the spectra and energy of several classes of graphs containing a linear polyene fragment are obtained. In [12], we obtain the energy of cross products of some graphs. In [15], the energy of iterated

(2)

line graphs of regular graphs and in [13], the energy of some self-complementary graphs are discussed.

The energy of regular graphs are discussed in [10]. Some works pertaining to the computation ofE(G) can be seen in [1, 6, 4, 11, 14].

As there is no easy way to find the eigenvalues of a graphG, the computation of the actual value ofE(G) is an interesting problem in graph theory. In this note we obtain analytic expressions for the energy of two classes of regular graphs.

All graph theoretic terminology is from [3]. We use the following lemmas and definitions in this paper.

Lemma 1. [3] LetM, N, P andQbe matrices with M invertible. Let S=

M N

P Q

. Then,|S|=|M|¯

¯Q−P M1

¯and ifM andP commutes, then,|S|=|M Q−P N| where the symbol|.|denotes the determinant.

Lemma 2. [3] LetGbe anr−regular connected graph onpvertices withAas an adjacency matrix and r=λ1, λ2, . . . , λmas the distinct eigenvalues. Then there exists a polynomialP(x)such thatP(A) =J whereJ is the all one square matrix of orderpandP(x)is given byP(x) =p×(x−λ(r−λ22)(x−λ)(r−λ33)...(r−λ)...(x−λmm)), so that P(r) =pandP(λi) = 0, for allλi6=r.

Lemma 3. [3]spec(Cp) =

2 2 cospj

1 1

andspec(Cp) =

p−3 −1−2 cosp j

1 1

, j= 1 to p−1.

Lemma 4. [3] Let G be an r− regular graph with an adjacency matrix A and incidence matrix R.

Then,RRT =A+rI.

Definition 1. Let G be a (p, q) graph. The complement of the incidence matrix R, denoted by R= [rij]is defined by

rij = 1 if vi is not incident withej

= 0, otherwise.

Definition 2. LetGbe a(p, q)graph. Corresponding to every edgeeofGintroduce a vertex and make it adjacent with all the vertices not incident with e in G. Delete the edges of G only. The resulting graph is called the partial complement of the subdivision graph of G, denoted by S(G).

(3)

Figure 1: S(C5)

2 Partial complement of the subdivision graph

In this section we obtain the spectrum of the partial complement of the subdivision graphS(G) of a regular graphGand the energy ofS(Cp).

Lemma 5. LetGbe anr−regular graph with an adjacency matrixAand incidence matrix R. Then, R=Jp×q−R , RT =Jq×p−RT andRRT = (q−2r)J + (A+r) where J is the all one matrix of appropriate order.

Proof. By Definition 1,R=Jp×q−R. Therefore

R RT = (Jp×q−R)¡

Jq×p−RT¢

=qJ−rJ−rJ+A+rI

= (q−2r)J+ (A+r)I, by Lemma 4.

Hence the lemma.

Lemma 6. Let Gbe a connectedr−regular (p, q)graph. Then, S(G)is regular if and only ifGis a cycle.

Proof. From Definition 2, we have the degree of vertices inS(G) corresponding to the edges of Gis p−2 each and of those corresponding to the vertices ofGisq−reach. SinceGisr−regular,q=pr2 and henceq−r=p−2 if and only ifr= 2. Thus, S(G) is regular if and only ifGis a cycle.

Theorem 1. Let Gbe a connectedr−regular (p, q)graph. Then, spec(S(G)) =

±p

p(q−2r) + 2r ±√

λi+r 0

1 1 q−p

, i= 2 top.

0 R

(4)

Theorem 2.

E¡ S(Cp

=















 2³

p−4 + 2 cot2pπ´

, p≡0(mod2)

p−4 + 2cosec 2pπ´

, p≡1(mod2)

Proof. By Lemma 3 and Theorem 1 we have

spec¡ S(Cp

=

p−2 −(p−2) ±2 cosπjp

1 1 1

, j= 1to p−1.

We shall consider the following two cases.

Case 1. p≡ 0(mod 2).

The cosine numbers 2cosπjp are positive only for πpj≤ π2. Then, the positive cosine numbers are 2 cosπp,2 cos³

π p ×2´

, ...,2 cos³

π p ×p2

´.

LetC= 2 cosπ p+ 2 cos

µπ p×2

+...+ 2 cos µπ

p×p 2

¶ and S= 2 sinπ

p+ 2 sin µπ

p×2

+...+ 2 sin µπ

p ×p 2

so that

C+iS = 2γ+ 2γ2+...+ 2γp2

= 2γ

¡1−γp2¢

1−γ whereγ= cosπ

p+isinπ

p andi=√

−1.

Now, equating real parts, we get C = cot2pπ −1. Since the spectrum of ¡ S(Cp

is symmetric with respect to zero, the energy contribution from the cosine numbers is 2C. Thus,

E¡ S(Cp

= 2×(p−2 + 2C)

= 2 µ

p−4 + 2 cot π 2p

Case 2. p≡1(mod2).

Whenpis odd, the cosine numbers 2cosπjp are positive forj≤p21. Then, by a similar argument as in Case 1, we getE(S(Cp)) = 2³

p−4 + 2 cosec2pπ´

. Hence the theorem.

(5)

3 Energy of the complement of a cycle.

In [5], I.Gutman obtained an analytic expression for the energy of a cycleCp. In this section we derive the energy ofCp, the complement of the cycleCp.

Theorem 3.

E¡ Cp

¢=































 2³

2p−9

3 +√

3 cotπp´

;p≡0(mod 3)

2 µ

2p8 3 +2 sin

π 3(1p1)

sinπp

;p≡1(mod 3)

2 µ

2p−10 3 +2 sin

π 3(1+1p)

sinπp

;p≡2(mod 3)

Proof. We havespec(Cp) =

p−3 −³

1 + 2 cos2πjp ´

1 1

, j= 1to p−1 by Lemma 3.

We shall consider the following cases.

Case 1. p≡0(mod3).

Then, −³

1 + 2 cos2πjp ´

≥0 if and only if p3 ≤j≤ 2p3. Let

2p 3

P

j=p3

³1 + 2 cos2πjp ´

=p+33 +

2p 3

P

j=p3

2 cos2πjp =p+33 +C and S=

2p 3

P

j=p3

2 sin2πjp , so thatC+iS=

2p 3

P

j=p3

γj whereγ= cosp +isinp. Equating real parts, we getC=−(1 +√

3cotπp).

The total sum of positive eigenvalues

=p−3 +√ 3 cotπ

p+ 1− µp+ 3

3

= 2p−9

3 +√

3 cotπ p. Thus,E(Cp) = 2×[2p39+√

3 cotπp].

The other two casesp≡1(mod3) andp≡2(mod3) can be proved similarly .

References

[1] R. Balakrishnan,The energy of a graph, Linear Algebra Appl.,387(2004), 287 - 295.

[2] C. A. Coulson, On the calculation of the energy in unsaturated hydrocarbon molecules, Proc.

(6)

[3] D.M.Cvetkovic, M. Doob, H. Sachs,Spectra of Graphs-Theory and Applications, Academic Press, (1980).

[4] I. Gutman, M. Milun, N. Trinajsti´c,H¨uckel Molecular Orbital Calculations of Aromatic Stabiliza- tion of Annulenes, Croat. Chem. Acta,44(1972), 207-213.

[5] I. Gutman, A graph theoretical study of conjugated systems containing a linear polyene frag- ment,Croat. Chem. Acta,48(2)(1976), 97 - 108.

[6] I. Gutman,The energy of a graph, Ber. Math. Statist. Sekt. Forschungszenturm Graz.,103(1978), 1 - 22.

[7] I. Gutman, O. E. Polansky,Mathematical Concepts in Organic Chemistry, Springer, 1986.

[8] I. Gutman,The energy of a graph: old and new results, in: A. Betten, A. Kohnert, R. Laue, A.

Wassermann (Eds.), Algebraic Combinatorics and Applications, Springer,(2000), 196-211.

[9] I. Gutman,Topology and stability of conjugated hydrocarbons. The dependence of total π-electron energy on molecular topology, J. Serb. Chem. Soc.,70(2005), 441-456.

[10] I. Gutman, S. Zare Firoozabadi, J. A. de la Pe˜na, J. Rada, On the energy of regular graphs, MATCH Commun. Math. Comput. Chem.,57(2007), 435-442.

[11] G. Indulal, A. Vijayakumar, On a pair of equienergetic graphs, MATCH Commun. Math.

Comput. Chem.,55(2006), 83 - 90.

[12] G. Indulal, A. Vijayakumar,Energies of some non-regular graphs, J. Math. Chem., ( to appear).

[13] G. Indulal, A. Vijayakumar,Equienergetic self-complementary graphs, Czechoslovak Math. J.,(to appear).

[14] O. E. Polansky,Uber unges¨¨ attigte monocyclen mit durchlaufender konjugation, 2. Mitt.: Berech- nung der elektronenstruktur mit hilfe der einfachen LCAO-MO-Methode und allgemeine gruppenthe- oretische betrchtungen, Monatsh. Chem. 91 (1960) 916-962

[15] H. S. Ramane, H. B. Walikar, S. B. Rao, B. D. Acharya, I. Gutman, P. R. Hampiholi, S. R. Jog, Equienergetic graphs, Kragujevac. J. Math.,26(2004), 5 - 13.

References

Related documents

Percentage of countries with DRR integrated in climate change adaptation frameworks, mechanisms and processes Disaster risk reduction is an integral objective of

This report provides some important advances in our understanding of how the concept of planetary boundaries can be operationalised in Europe by (1) demonstrating how European

The Congo has ratified CITES and other international conventions relevant to shark conservation and management, notably the Convention on the Conservation of Migratory

SaLt MaRSheS The latest data indicates salt marshes may be unable to keep pace with sea-level rise and drown, transforming the coastal landscape and depriv- ing us of a

Six leptocephali, belonging to various genera, were collected from the shore seines of Kovalam beach (7 miles south of Trivandrum) in the month of January 1953. Of these 2

These gains in crop production are unprecedented which is why 5 million small farmers in India in 2008 elected to plant 7.6 million hectares of Bt cotton which

INDEPENDENT MONITORING BOARD | RECOMMENDED ACTION.. Rationale: Repeatedly, in field surveys, from front-line polio workers, and in meeting after meeting, it has become clear that

To break the impasse, the World Bank’s Energy Sector Management Assistance Program (ESMAP), in collaboration with Loughborough University and in consultation with multiple