Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 35–40
Large sets of long distance equienergetic graphs∗
Dragan Stevanović
University of Primorska — FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
and
Mathematical Institute, Serbian Academy of Science and Arts,
Knez Mihajlova 36, 11000 Belgrade, Serbia
Received 2 December 2008, accepted 2 January 2009, published online 11 March 2009
Abstract
Distance energy of a graph is a recent energy-type invariant, defined as the absolute
deviation of the eigenvalues of the distance matrix of the graph. Two graphs of the same
order are said to be distance equienergetic if they have equal distance energy, while they
have distinct spectra of their distance matrices. Examples of pairs of distance equienergetic
graphs appear in the literature already, but most of them have diameter two only.
We describe here the distance spectrum of a special composition of regular graphs,
and, as an application, we show that for any n ≥ 3, there exists a set of n + 1 distance
equienergetic graphs which have order 6n and diameter n− 1 each.
Keywords: Distance spectrum, distance energy, join, regular graphs.
Math. Subj. Class.: 05C50
1 Introduction
Let G = (V,E) be a simple graph with n vertices V = {v1, v2, . . . , vn}. The energy of a
graph E = E(G) =
∑n
i=1 |λi|, where λi, i = 1, . . . , n are the eigenvalues of an adjacency
matrix of G, has well-known chemical applications [3, 4, 5, 6]. Following the recent defi-
nition of the Laplacian energy in [7], it was observed that other energy-type invariants can
be defined as the absolute deviation of eigenvalues from their average value for a suitable
graph matrix. Let dG(vi, vj) denote the length of the shortest path between the vertices vi
and vj of G. The matrix D(G) = (dG(vi, vj)), indexed by the vertices of G, is the dis-
tance matrix of G. Since its trace is zero, we can define the distance energy DE(G) of G
as the sum of absolute values of the eigenvalues of the distance matrix D(G). The dis-
tance energy, together with a handful of other invariants, has been studied by Consonni and
∗This work was supported by the research program P1-0285 of the Slovenian Agency for Research and the
research grant 144015G of the Serbian Ministry of Science.
E-mail address: dragan.stevanovic@upr.si (Dragan Stevanović)
Copyright c© 2009 DMFA
36 Ars Math. Contemp. 2 (2009) 35–40
Todeschini [1] for possible use in QSPR modelling. Their study reveals that the distance
energy is a useful molecular descriptor: the values DE(G) or DE(G)/n appear among
the best univariate models for the motor octane number of the octane isomers or the water
solubility of polychlorobiphenyls.
Two graphs of the same order are said to be distance equienergetic if they have equal
distance energy, while they have distinct distance spectra. Examples of distance equiener-
getic graphs appear in the literature [8, 9, 10], but most of them have diameter two only.
We show here that new pairs of distance equienergetic graphs can be constructed as com-
positions of regular graphs.
The particular composition that we consider is defined as follows. Let Gi = (Vi, Ei),
i = 1, . . . , n be arbitrary finite graphs. The joined union G[G1, . . . , Gn] is the graph
H = (W,F ) with:
W =
n⋃
i=1
Vi,
F =
n⋃
i=1
Ei ∪
⋃
(vi,vj)∈E
Vi × Vj .
In other words, the joined union is obtained from the union of graphsG1, . . . ,Gn by joining
with an edge each pair of a vertex from Gi and a vertex from Gj whenever vi and vj are
adjacent in G. For example, the usual join of two graphs G and H is a special case of the
joined union: K2[G,H], where K2 is the complete graph on two vertices.
In the next section, we describe the distance spectrum of the joined union of regular
graphs in the terms of their adjacency spectrum and the eigenvalues of the auxiliary matrix,
determined by the graph G. Then in Section 3 we show that the sets of graphs with equal
distance energy can be constructed as a joined union of regular graphs for which all adja-
cency eigenvalues are at least −2. As an example, we show that for any n ≥ 3, there exists
a set of n+ 1 distance equienergetic graphs which have order 6n and diameter n− 1 each.
2 The distance spectrum of the joined union
Theorem 2.1. Let G = (V,E) be a simple graph with n vertices v1, . . . , vn, and for
i = 1, . . . , n, let Gi = (Vi, Ei) be an ri-regular graph of order mi and eigenvalues of the
adjacency matrix AGi : λi,1 = ri ≥ λi,2 ≥ · · · ≥ λi,mi . The distance spectrum of the
joined union G[G1, . . . , Gn] consists of the eigenvalues −λi,j − 2 for i = 1, . . . , n and
j = 2, 3, . . . ,mi and the eigenvalues of the matrix
2m1 − r1 − 2 dG(v1, v2)m2 dG(v1, v3)m3 . . . dG(v1, vn)mn
dG(v2, v1)m1 2m2 − r2 − 2 dG(v2, v3)m3 . . . dG(v2, vn)mn
dG(v3, v1)m1 dG(v3, v2)m2 2m3 − r3 − 2 . . . dG(v3, vn)mn
. . . . . . . . . . . .
dG(vn, v1)m1 dG(vn, v2)m2 dG(vn, v3)m3 . . . 2mn − rn − 2
 . (2.1)
Proof. The distance matrix D(H) of the joined union H = G[G1, . . . , Gn] is a block
D. Stevanović: Large sets of long distance equienergetic graphs 37
matrix of the form
D(H) =

2(J − I)−AG1 dG(v1, v2)J . . . dG(v1, vn)J
dG(v2, v1)J 2(J − I)−AG2 . . . dG(v2, vn)J
. . . . . . . . . . . .
dG(vn, v1)J dG(vn, v2)J . . . 2(J − I)−AGn
 ,
where I and J are the unit and the all-one matrices of corresponding orders.
First, let i ∈ {1, . . . , n}. As a regular graph, Gi has all-one vector j as an eigenvector
of the adjacency matrix AGi corresponding to the eigenvalue ri, while other eigenvectors
are orthogonal to j. (Note that Gi need not be connected, and thus, ri need not be a
simple eigenvalue of Gi.) Let λ be an arbitrary eigenvalue of AGi with the corresponding
eigenvector x, such that jTx = 0. Then the vector y, given by
yu =
{
xu, u ∈ Vi
0, u /∈ Vi
is an eigenvector of D(H) corresponding to the eigenvalue −λ − 2: since y has zeros at
coordinates corresponding to
⋃
j 6=i Vj , we have
D(H)y =

dG(v1, vi)J
. . .
dG(vi−1, vi)J
2(J − I)−AGi
dG(vi+1, vi)J
. . .
dG(vn, vi)J

x =

dG(v1, vi)Jx
. . .
dG(vi−1, vi)Jx
2Jx− 2x−AGix
dG(vi+1, vi)Jx
. . .
dG(vn, vi)Jx

= −(2 + λ)y.
There exists a total of (
∑n
i=1 |Vi|) − n mutually orthogonal eigenvectors of D(H) of this
form. Moreover, they are all orthogonal to the vectors
(ji)u =
{
1, u ∈ Vi
0, u /∈ Vi
i = 1, . . . , n.
In particular, this means that the vectors j1, j2, . . . , jn are spanned by the n remaining
eigenvectors of D(H), which, due to the fact that j1, j2, . . . , jn are linearly independent,
implies that the remaining eigenvectors of D(H) have the form
∑n
i=1 αij
i for suitable
coefficients α1,. . . ,αn.
Let ν be an eigenvalue ofD(H) with an eigenvector of the form
∑n
i=1 αij
i. Then from
AGij = rij, i = 1, . . . , n, we have
D(H)
n∑
i=1
αij
i =
n∑
i=1
αiD(H)ji =
n∑
i=1
αi

dG(v1, vi)J
. . .
dG(vi−1, vi)J
2(J − I)−AGi
dG(vi+1, vi)J
. . .
dG(vn, vi)J

j
=
n∑
i=1
αi
(2mi − ri − 2)ji +∑
k 6=i
dG(vk, vi)mijk

38 Ars Math. Contemp. 2 (2009) 35–40
=
n∑
i=1
(2mi − ri − 2)αi +∑
k 6=i
dG(vi, vk)mkαk
 ji = ν n∑
i=1
αij
i.
From the last equality we get the system of equations in α1, . . . , αn:
(2mi − ri − 2− ν)αi +
∑
k 6=i
dG(vi, vk)mkαk = 0, i = 1, . . . , n, (2.2)
which may have a nontrivial solution only if its determinant is equal to zero, i.e., only if
ν is an eigenvalue of (2.1). Further, it is obvious from above that any nontrivial solution
of (2.2) forms an eigenvector of D(H) corresponding to eigenvalue ν. Since all n remain-
ing eigenvectors of D(H) must be formed in this way, we conclude that each eigenvalue
of (2.1) is an eigenvalue of D(H) as well.
For example, let G be an r1-regular graph of order n1 and the eigenvalues λ1 = r1 ≥
λ2 ≥ · · · ≥ λn1 of its adjacency matrix, and let H be an r2-regular graph of order n2 and
the eigenvalues µ1 = r2 ≥ µ2 ≥ · · · ≥ µn2 of its adjacency matrix. From the previous
theorem, the distance spectrum of the join G∇H , which is the same as K2[G,H], consists
of the eigenvalues −λi − 2 for i = 2, . . . , n1, then −µj − 2 for j = 2, . . . , n2, and two
eigenvalues (m1−r1/2)+(m2−r2/2)−2±
√
((m1 − r1/2)− (m2 − r2/2))2 +m1m2.
3 Long distance equienergetic graphs
Sets of graphs with equal distance energy can be constructed as a joined union of regular
graphs for which all adjacency eigenvalues are at least −2, when the corresponding eigen-
values−λ−2 of the distance matrix are always negative. Such graphs are, for example, the
empty graph Km, the complete graph Km, the cycle Cm, as well as regular line graphs [2]
(which are itself line graphs of regular or semiregular graphs). For such graphs, we can use
the well-known fact that the sum of all adjacency eigenvalues is 0 (see, e.g., [2]) in order
to determine the distance energy of the joined union.
Theorem 3.1. Let G = (V,E) be a simple graph with n vertices v1, . . . , vn, and for
i = 1, . . . , n, let Gi and Hi be ri-regular graphs of order mi whose smallest eigenvalue of
the adjacency matrix is at least −2. Then
DE(G[G1, . . . , Gn]) = DE(G[H1, . . . ,Hn]).
Proof. Since graphs Gi and Hi, i = 1, . . . , n, have the same order mi and the degree ri,
both joined unions G[G1, . . . , Gn] and G[H1, . . . ,Hn] have the same auxiliary matrix
2m1 − r1 − 2 dG(v1, v2)m2 dG(v1, v3)m3 . . . dG(v1, vn)mn
dG(v2, v1)m1 2m2 − r2 − 2 dG(v2, v3)m3 . . . dG(v2, vn)mn
dG(v3, v1)m1 dG(v3, v2)m2 2m3 − r3 − 2 . . . dG(v3, vn)mn
. . . . . . . . . . . .
dG(vn, v1)m1 dG(vn, v2)m2 dG(vn, v3)m3 . . . 2mn − rn − 2
 ,
so that the corresponding part of their distance spectra is equal, and adds the same amount
M to the distance energy of joined unions.
D. Stevanović: Large sets of long distance equienergetic graphs 39
Next, for i = 1, . . . , n, let Gi has eigenvalues of the adjacency matrix λi,1 = ri ≥
λi,2 ≥ · · · ≥ λi,mi ≥ −2, and let Hi has eigenvalues of the adjacency matrix µi,1 = ri ≥
µi,2 ≥ · · · ≥ µi,mi ≥ −2. The remaining distance eigenvalues of G[G1, . . . , Gn] are of
the form −λi,j − 2 for i = 1, . . . , n and j = 2, . . . ,mi. Since λi,j ≥ −2 we have that
| − λi,j − 2| = λi,j + 2. Then from
∑mi
j=1 λi,j = 0, we get
n∑
i=1
mi∑
j=2
| − λi,j − 2| =
n∑
i=1
mi∑
j=2
λi,j
+ 2(mi − 1) = n∑
i=1
−ri + 2(mi − 1).
For the remaining distance eigenvalues −µi,j − 2 of G[H1, . . . ,Hn], i = 1, . . . , n, j =
2, . . . ,mi, we similarly get
n∑
i=1
mi∑
j=2
| − µi,j − 2| =
n∑
i=1
−ri + 2(mi − 1).
Therefore,
DE(G[G1, . . . , Gn]) = M +
n∑
i=1
2mi − ri − 2 = DE(G[H1, . . . ,Hn]).
In the above theorem, the graphs G[G1, . . . , Gn] and G[H1, . . . ,Hn] share the auxil-
iary matrix and have a common part of the distance spectra. Therefore, in order for these
graphs to be distance equienergetic, it is necessary that the union of adjacency spectra of
G1, . . . , Gn, with vertex degree being deleted from each adjacency spectrum, is different
from the union of adjacency spectra of H1, . . . ,Hn.
Example
Let Pn and Cn be the path and the cycle of order n, respectively. As an application of
Theorem 3.1, we observe that, for each n ≥ 3, the following is a set of n + 1 distance
equienergetic graphs of order 6n and diameter n− 1:
{ Pn[C6, C6, . . . , C6, C6],
Pn[C6, C6, . . . , C6, C3 ∪ C3],
Pn[C6, C6, . . . , C3 ∪ C3, C3 ∪ C3],
. . . ,
Pn[C6, C3 ∪ C3, . . . , C3 ∪ C3, C3 ∪ C3],
Pn[C3 ∪ C3, C3 ∪ C3, . . . , C3 ∪ C3, C3 ∪ C3] }.
Since both C6 and C3 ∪C3 are 2-regular graphs of order 6, all graphs above have the same
auxiliary matrix (2.1), and thus, share this part of the distance spectra. The remaining part
of the distance spectrum of Pn[C6, . . . , C6︸ ︷︷ ︸
k
, C3 ∪ C3, . . . , C3 ∪ C3︸ ︷︷ ︸
n−k
], 0 ≤ k ≤ n, is
[−4n−k,−32k,−14n−2k, 0k],
with exponents denoting the multiplicities, showing that no two graphs above are cospec-
tral.
40 Ars Math. Contemp. 2 (2009) 35–40
References
[1] V. Consonni and R. Todeschini, New Spectral Indices for Molecule Description, MATCH Com-
mun. Math. Comput. Chem. 60 (2008), 3–14.
[2] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs—Theory and Application, 3rd edition,
Johann Ambrosius Barth Verlag, 1995.
[3] I. Gutman, The energy of a graph, Ber. Math. Statist. Sekt. Forschungsz. Graz 103 (1978), 1–22.
[4] I. Gutman, The energy of a graph: old and new results, in: A. Betten, A. Kohnert, R. Laue and
A. Wassermann (eds.), Algebraic Combinatorics and Applications, Springer-Verlag, Berlin,
2001, 196–211.
[5] 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.
[6] I. Gutman, Total π-electron energy of benzenoid hydrocarbons, Topics Curr. Chem. 162 (1992),
29–63.
[7] I. Gutman and B. Zhou, Laplacian energy of a graph, Linear Algebra Appl. 414 (2006), 29–37.
[8] G. Indulal and I. Gutman, On the distance spectra of some graphs, Math. Commun.—Univ. of
Croatia 13 (2008), 123–131.
[9] G. Indulal, I. Gutman and A. Vijayakumar, On Distance Energy of Graphs, MATCH Commun.
Math. Comput. Chem. 60 (2008), 461–472.
[10] H. S. Ramane, I. Gutman and D. S. Revankar, Distance Equienergetic Graphs, MATCH Com-
mun. Math. Comput. Chem. 60 (2008), 473–484.