Intelligent Information Management, 2009, 1, 120-121
doi:10.4236/iim.2009.12017 Published Online November 2009 (http://www.scirp.org/journal/iim)
Frucht Graph is not Hyperenergetic
S. PIRZADA
Department of Mathematics, University of Kashmir, Kashmir, India
Abstract: If 12
, ,...,
p

 are the eigen values of a p-vertex graph , the energy of is G G
1
()
p
i
i
EG


.
If , then is said to be hyperenergetic. We show that the Frucht graph, the graph used in
the proof of well known Frucht’s theorem, is not hyperenergetic. Thus showing that every abstract group is
isomorphic to the automorphism group of some non-hyperenergetic graph. AMS Mathematics Subject Clas-
sification: 05C50, 05C35
() 2EG 2pG
Keywords: energy of a graph, hyperenergetic, frucht graph, automorphism
1. Introduction
The concept of hyperenergetic graphs was introduced by
Gutman [1]. The existence of hyperenergetic graphs has
been known for quite some time, their systematic design
was first achieved by Walikar et al. [2]. Details can also
be seen in [3–6].
The following result can be found in [4].
Theorem 1. A graph with p vertices and m edges such
that is not hyperenergetic.
2mp2
In this paper, we give the existence of one more class
of hyperenergetic graphs, called the Frucht graphs.
2. Frucht Graph is not Hyperenergetic
Let Γ be a group with n elements and Λ be a set of Γ not
containing the identity e. The Cayley digraph is defined
to be the digraph with vertex set VГ and arc set 
{(,) :
A
ggh h
KK
Λ}. It is denoted by Γ, Λ). If Λ
= Γ -e, the resulting Cayley digraph is complete and is
denoted by . If Λ is a set of generators for Γ,
the Cayley digraph is called the basic Cayley digraph.
(DD
(, )

In the Cayley digraph (DD

Γ, Λ), if (,)
g
h
1
gk

is an
arc, for some , that is kghh

 and
1
g
k
 is called the color of (,)
g
k.
An automorphism of is said to be color preserv-
ing if it preserves the colors of the arcs. It is well known
that the group of color preserving automor-
phisms of the Cayley digraph Γ, Λ) is isomor-
phic to Γ.
D
()CD
(DD
The following result is the Frucht’s Theorem [7–9].
Theorem 2. Every group is isomorphic to the auto-
morphism group of some graph.
While proving Theorem 2, Frucht obtained the graph
from Γ, Λ) called as Frucht graph, whose auto-
morphism group is isomorphic to .
1
G(D
()CD
The following is the construction of Frucht graph .
1
G
Replace each arc ij
g
g of by a figure joining
vertices
D
i
g
and
j
g
. The figure consists of the 3-path
iii j
g
uvg
21k
, and two paths- a path (containing
vertices) rooted at , and a path (containing
2k
p
p
2k
i
u21k

vertices) rooted at , where
i
v1
ij k
g
g
g

is the
color of ij
g
g. (Note that there will be a similar figure
corresponding to
j
i
g
g for a different k).
Clearly, the Frucht graph with
1()Gs

 has
(1)(21)ns s

 vertices.
Theorem 3. The Frucht graph has
1
G(2 1)ns s

edges.
Proof. The number of edges in is given
by
m1()G
11
4( 1)
(41)(2 1)
2
ns
ik
ss
mkn snss




 



Theorem 4. The Frucht graph is not hyperener-
getic.
1
G
Proof. We observe that,


(21)2(1)(2)222mnssns sp

 .
Thus the result follows from Theorem 1.
Lovasz [10] gives an alternate construction of the

J. WU ET AL. 121
graph used to prove the Fruchts theorem. In this
case the figure of color is a path of length
2()G
k2k

,
including the end vertices i
g
and
j
g
, in which to the
first internal vertices are attached a path and to
the last internal vertex (near
k2 P
j
g
) is attached a path .
3
P
Theorem 5. has vertices,
where
2()G2
(41ns s)
s
 .
Proof. In each arc
2()Gij
g
g
4k
is replaced by a
figure with internal vertices(that is
excluding
12kk
i
3 3 
g
and j
g
) if 1
ijk
g
gg
.
Therefore total number of extra vertices introduced to
form is equal to
2()G
22
11 1
(23)(4 )(4 )
ns n
ik i
kssns
 
 
 s
Hence 22
2
(())( 4)( 41)VGnssn nss .
Theorem 6. has edges, where
2()G2
(5ns s)
s
 .
Proof. The number of edges in is given by
2()G
22
11 1
(22)( 5)( 5
ns n
ik i
mkk ssns
 

 )s
2
.
Theorem 7. is not hyperenergetic.
2()G
Proof. We see that
22
(5)2(41)22mns snssp

 
.
Thus the result follows from Theorem 1.
Combining the above observations, we conclude with
the following result.
Theorem 8. Every group is isomorphic to the auto-
morphism group of some non-hyperenergetic graph.
REFERENCES
[1] I. Gutman, “The energy of a graph,” Journal of the Ser-
bian Chemical Society, Vol. 64, pp. 199–205, 1999.
[2] L. Lovasz, “Combinatorial problems and exercises,”
North-Holland, Amsterdam, 1979.
[3] I. Gutman and L. Pavlovic, “The energy of some graphs
with large number of edges,” Bull. Acad. Serbe Sci. Arts,
Vol. 118, pp. 35–50, 1999.
[4] I. Gutman Y. Hou, H. B. Walikar, H. S. Ramane, and P. R.
Hamphiholi, “No huckel graph is hyperenergetic,” Jour-
nal of the Serbian Chemical Society, Vol. 65, No. 11, pp.
799–801, 2000.
[5] I. Gutman, “The energy of a graph, old and new results,”
In: A. Betten, et al., Algebraic Combinatorics and its Ap-
plications, Springer-Verlag, Berlin, pp.196–211, 2001.
[6] I. Gutman and L. Pavlovic, “The energy of some graphs
with large number of edges,” Bull. Acad. Serbe Sci. Arts,
Vol. 118, pp. 35–50, 1999.
[7] R. Frucht, “Herstellung von graphin mit vorgege bener
abstakten Gruppe,” Compositio Mathematica, Vol. 6, pp.
239–250, 1938.
[8] R. Frucht, “Graphs of degree three with a given abstract
group,” Canadian Journal Mathematics, Vol. 1, pp.
365–378, 1949.
[9] R. Frucht and F. Harary, “On the corona of two graphs,”
Aequationes mathematicae, Basel, Vol. 4, pp. 322–325,
1970.
[10] J. Koolen, V. Moulton, I. Gutman, and D. Vidovic, “More
hyperenergetic molecular graphs,” Journal of the Serbian
Chemical Society, Vol. 65, pp. 571–575, 2000.
[11] H. B. Walikar, H. S. Ramane, and P. R. Hamphiholi, “On
the energy of a graph,” Proceedings of Conference on
Graph Connections (R. Balakrishnan et al. eds.), Allied
Publishers, New Delhi, pp. 120–123, 1999.