J.
Indones.
Math.
Soc.
Vol.
No.
, pp.
15Ae21.
ENERGY OF COMPLEMENT OF STARS
Hampiholi1 .
Walikar2 , and B.
Durgi3 Department of Master of Computer Applications.
Gogte Institute of Technology.
Udyambag.
Belgaum - 590008.
India prhampi@yahoo.
Department of Computer Science.
Karnatak University.
Dharwad - 580003.
India walikarhb@yahoo.
Department of Mathematics.
KLE College of Engineering and Technology.
Belgaum - 590008.
India durgibs@yahoo.
Abstract.
The concept of energy of a graph was put forward by I.
Gutman in 1978 .
The characteristic polynomial of a graph G with p vertices is defined as i(G : ) = det(I Oe A(G), where A(G) is the adjacency matrix of G and I is the unit matrix.
The roots of the characteristic equation i(G : ) = 0, denoted by 1 , 2 , .
, p are the eigenvalues of G.
The energy E = E(G) of a graph G is defined as Oc .
| E(G) = The graphs with large number of edges are referred as graph represenation of inorganic clusters, called as cluster graphs.
In this paper we obtain the characteristic polynomial and energy of class of cluster graphs which are termed as complement of stars.
Key words and Phrases: Spectra of graphs, energy of graphs, stars, cluster graphs.
2000 Mathematics Subject Classification: 05C50 Received: 23-10-2012, revised: 03-12-2012, accepted: 03-01-2013.
Hampiholi.
Walikar, and B.
Durgi Abstrak.
Konsep energi dari sebuah graf dikemukakan oleh I.
Gutman in 1978 .
Polinom karakteristik dari sebuah graf G dengan p buah titik didefinisikan sebagai i(G : ) = det(I Oe A(G), dengan A(G) adalah matriks ketetanggaan dari G dan I adalah matriks satuan.
Akar dari persamaan karakteristik i(G : ) = 0, dinotasikan dengan 1 , 2 , .
, p adalah nilai eigen dari G.
Energi E = E(G) dari sebuah graf
G didefinisikan sebagai Oc
E(G) =
Graf dengan sisi yang banyak yang dinyatakan sebagai penyajian graf dari klusterkluster anorganik, disebut sebagai graf-graf kluster.
Pada paper ini kami mendapatkan polinom karakteristik dan energi dari kelas graf-graf kluster yang diistilahkan dengan komplemen dari graf bintang.
Kata kunci: Spektrum dari graf-graf, energi of graf-graf, graf bintang, graf kluster.
Introduction Let G be a simple undirected graph with p vertices and q edges.
Let V (G) = .
1 , v2 , .
, vp } be the vertex set of G.
The adjacency matrix of G is defined as A(G) = .
ij ], where aij = 1 if vi is adjacent to vj and aij = 0, otherwise.
The characteristic polynomial of G is i(G : ) = det(I Oe A(G)),where I is unit matrix of order p.
The roots of the equation i(G : ) = 0 denoted by 1 , 2 , .
, p are the eigenvalues of G and their Ocp collection is the spectrum of G .
The energy .
of G is defined as E(G) = i=1 .
The spectrum of the complete graph Kp is .
Oe 1, and Oe 1.
Oe .
Consequently E(Kp ) = 2.
Oe .
It was conjectured some years ago that, among all graphs with p vertices the complete graph has the greatest energy .
But this is not true .
There are graphs having energy greater than E(Kp ).
The graph G with E(G) > E(Kp ) is referred as hyperenergetic graph, otherwise known as non-hypernergetic .
Some Edge Deleted Cluster Graphs Gutman and L.
PavlovicA .
introduced four classes of graps obtained from compete graph by deleting edges.
For the sake of continuity we recall these here.
Definition 2.
Let v be a vertex of the complete graph Kp , p Ou 3 and let ei , i = 1, 2, .
, k, 1 O k O p Oe 1, be its disdinct edges, all being incident to v.
The graph Kap .
r Cl.
, .
) is obtained by deleting ei , i = 1, 2, .
, k from Kp .
addition Kap .
O = Kp .
Definition 2.
Let fi , i = 1, 2, .
, k, i O k O UOp/2UU be independent edges of the complete graph Kp , p Ou 3.
The graph Kbp .
is obtained by deleting edges fi , i = 1, 2, .
, k from Kp .
The graph Kbp .
O = Kp .
Energy of Complement Stars Definition 2.
Let complete graph Kk be the induced subgraph of Kp , 2 O k O p, p Ou 3.
The graph Kcp .
is obtained by deleting from Kp all the edges of Kk .
In addition Kcp .
O = Kcp .
O = Kp .
Definition 2.
Let 3 O k O p, p Ou 3.
The graph Kdp .
obtained from Kp , by deleting the edges belonging to a k-membered cycle.
Theorem 2.
For 0 O k O p Oe 1, i(Cl.
, .
: ) = ( .
pOe3 .
Oe .
Oe .
2 Oe .
p Oe k Oe .
Oe .
Oe 1 Oe .
] .
Theorem 2.
For p Ou 3 and 0 O k O UOp/2UU, i(Kbp .
: ) = k ( .
pOe2kOe1 ( .
kOe1 .
Oe .
Oe .
Oe 2.
Oe k Oe .
] .
Theorem 2.
For p Ou 3 and 2 O k O p, i(Kcp .
: ) = kOe1 ( .
pOekOe1 .
Oe .
Oe k Oe .
Oe k.
Oe .
] .
Theorem 2.
For p Ou 3 and 3 O k O p, pOekOe1 i(Kdp .
: ) = ( .
[ Oe.
Oe.
Oe.
pOe2kOe.
] kOe1 Oa( 2cos We introduce here another class of graphs obtained from Kp and we denote it by Cl.
, m, .
Two subgraphs G1 and G2 of graph G are independent subgraphs if V (G1 ) O V (G2 ) is an empty set.
Definition 2.
Let K1,mOe1 be a star graph.
Let Kp be a complete graph on p The graph obatined by deleting k independent stars (K1,mOe1 ) from Kp will be denoted by Cl.
, m, .
In addition for k = 1.
Cl.
, m, .
= Cl.
, .
Definition 2.
Let K1,m1 Oe1 and K1,m2 Oe1 be star graphs.
The graph obatined by deleting the edges of k1 independent stars (K1,m1 Oe1 ) and edges of k2 independent stars (K1,m2 Oe1 ) from Kp denoted by Cl.
, .
1 , k1 ), .
2 , k2 )).
In addition for k2 = 0, m1 = m, k1 = k.
Cl.
, .
1 , k1 ), .
2 , k2 )) O = Cl.
, m, .
Hampiholi.
Walikar, and B.
Durgi Now we proceed to prove the main result in the form of Theorem 2.
11 and Theorem 2.
Theorem 2.
Let p, m, k be positive integers.
Let mk O p.
Then the characteristic polynomial of Cl.
, m, .
is i(Cl.
, m, .
: ) ( .
pOe2kOe1 [( .
2 Oe .
Oe .
]kOe1 .
Oe .
Oe .
mk Oe 2p Oe 2k Oe m .
Oe m.
Oe .
Proof.
Without loss of generality let k independent stars of order m of Cl.
, m, .
be situated as follows.
For j = 0, 1, .
, k Oe 1, on each of the vertices vjm 1 , m Oe 1 vertices vjm i , i = 2, 3, .
, m are incident.
Let the adjacency matrix of Cl.
, m, .
be A.
The characteristic polynomial of Cl.
, m, .
is det(I Oe A).
For convinience, we compute det(AOeI) and then multiply by (Oe.
p to be the final result.
Therefore the characteristic polynomial of Cl.
, m, .
is the following determinant.
Subtracting first column from all other columns and setting 1 = X, in the above determinant, we obtain .
Energy of Complement Stars Oe OeX Oe1 Oe1 OeX Oe1 Oe1 OeX OeX Oe1 Oe1 OeX Oe1 Oe1 OeX OeX OeX OeX Then performing the following sequence of operations on .
Ri Oe Rm for i = 2, 3, .
, m Oe 1 and R1 Oe ( .
Rm .
C1 CXi for i = mk 1, mk 2, .
, p, we get Cl.
, m, .
= = |M ||Q| .
as P is zero block.
Simplifying |Q| of .
we obtain i(Cl.
, m, .
: ) = (OeX)pOemk |M | Again performing next set of operations on |M | sequentially.
Adding columns Cjm 1 , for j = 1, 2, .
, k Oe 1 to the first column C1 .
Multiplying X to columns Cjm 1 , j = 1, 2, .
, kOe1 and dividing by X kOe1 .
OckOe1 Performing Cim 1 Oe j=2 Cim j , i = 1, 2, .
, k Oe 1.
OckOe1 Cim 1 Performing C1 i=1 .
Oe.
OeX Putting X = 1, multiplying by (Oe.
p and simplifying, we get the result of Theorem 2.
Performing similar set of opeartions on det(I Oe Cl.
, .
1 , k1 ), .
2 , k2 ))) we obtain the characteristic polynomial of Cl.
, .
1 , k1 ), .
2 , k2 )).
We state this formally in the following theorem.
Theorem 2.
Let p, m1 , k1 , m2 , k2 be positive integers.
Let m1 k1 m2 k2 O p.
Then the characteristic polynomial of Cl.
, .
1 , k1 ), .
2 , k2 )) is Hampiholi.
Walikar, and B.
Durgi i(Cl.
, .
1 , k1 ), .
2 , k2 )) : ) = X pOe2.
1 k2 ) [.
1 Oe.
OeX 2 ]k1 Oe1 [.
2 Oe.
OeX 2 ]k2 D where D = [ Oe .
1 Oe .
] Oe Z.
2 Oe .
1 Oe .
] Z = k1 k2 Oe1 p Oe .
1 k1 m2 k2 ) .
1 Oe .
[X Oe .
1 Oe .
] k2 [X Oe .
2 Oe .
] .
1 Oe .
Oe X 2 .
2 Oe .
Oe X 2 Here we give some examples in Table 1 and Table 2.
Table 1.
Characteristic polynomial of Cl.
, .
1 , k1 ), .
2 , k2 )) .
, .
1 , k1 ), .
2 , k2 )) .
, .
, .
, .
, .
) .
, .
, .
, .
, .
) .
, .
, .
, .
, .
) .
, .
, .
, .
, .
) .
, .
, .
, .
, .
) Characteristic equation of Cl.
, .
K1 ), .
2 , k2 )) 4 Oe 22 = 0 ( .
Oe 32 Oe 5 .
= 0 .
33 22 ).
Oe 32 Oe 10 .
= 0 .
44 53 22 ).
Oe 42 Oe 12 .
= 0 .
Oe 45 Oe 274 Oe 243 122 ).
3 42 Oe .
= 0 Table 2.
Energy of Cl.
, .
1 , k1 ), .
2 , k2 )) .
, .
1 , k1 ), .
2 , k2 )) .
, .
, .
, .
, .
) .
, .
, .
, .
, .
) .
, .
, .
, .
, .
) .
, .
, .
, .
, .
) .
, .
, .
, .
, .
) Spectra of G = Cl.
, .
1 , k1 ), .
2 , k2 )) Oe2, 0, 0, 2 Oe1.
Oe1.
Oe1.
Oe1, 0.
4827, 4.
Oe2.
Oe2.
Oe1, 0, 0, 0.
3649, 4.
Oe2.
Oe2.
Oe1.
Oe1, 0, 0, 0.
5729, 5.
Oe2.
Oe2.
Oe2.
Oe1.
Oe1, 0, 0, 0.
3531, 0.
4142, 7.
Energy E(G) Remarks:
For m1 = m, k1 , = k, k2 = 0.
Cl.
, .
1 , k1 ), .
2 , k2 ) O = Cl.
, m, .
For m1 Oe 1 = k, k1 , = 1, k2 = 0.
Cl.
, .
1 , k1 ), .
2 , k2 ) O = Cl.
, .
For m1 = 2, k1 , = k, k2 = 0.
Cl.
, .
1 , k1 ), .
2 , k2 ) O = Kbp .
For m1 = 1, k1 , = 0, k2 = 0.
Cl.
, .
1 , k1 ), .
2 , k2 ) O = Kp Acknowledgement.
The author PRH is thankful to Gogte Institute of Technology.
Belgaum.
India and Visvesvaraya Technological University.
India, for their Energy of Complement Stars support through financial assiatance and support through Research Grants Scheme (No.
VTU/Aca-RGS/2008-2009/7.
References