Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 93–100
Distance spectrum of graph compositions∗
Gopalapillai Indulal
Department of Mathematics, St. Aloysius College, Edathua
Alappuzha–689573, India
Received 20 March 2009, accepted 15 May 2009, published online 19 June 2009
Abstract
The D-eigenvalues {µ1, µ2, . . . , µp} of a graph G are the eigenvalues of its distance
matrix D and form the distance spectrum or D-spectrum of G denoted by specD(G). In
this paper we obtain theD-spectrum of the cartesian product of two distance regular graphs.
TheD-spectrum of the lexicographic productG[H] of two graphsG andH whenH is reg-
ular is also obtained. The D-eigenvalues of the Hamming graphs Ham(d, n) of diameter
d and order nd and those of the C4 nanotori, Tk,m,C4 are determined.
Keywords: Distance spectrum, Cartesian product, lexicographic product, Hamming graphs, C4 nan-
otori.
Math. Subj. Class.: 05C12, 05C50
1 Introduction
Adjacency matrix of a graph and its spectrum have arisen as a natural tool with which one
can study graphs and its structural properties. Also the adjacency spectrum find applica-
tions in quantum theory and chemistry [3]. The idea of distance matrix seems a natural
generalization, with perhaps more specificity than that of an adjacency matrix. Distance
matrix and their spectra have arisen independently from a data communication problem
[7] studied by Graham and Pollack in 1971 in which the most important feature is the
number of negative eigenvalues of the distance matrix. While the problem of computing
the characteristic polynomial of adjacency matrix and its spectrum appears to be solved
for many large graphs, the related distance polynomials have received much less attention.
The distance matrix is more complex than the ordinary adjacency matrix of a graph since
the distance matrix is a complete matrix (dense) while the adjacency matrix often is very
sparse. Thus the computation of the characteristic polynomial of the distance matrix is
∗This work was supported by the University Grants Commission of Government of India under the minor
research project grant No: MRP(S)-399/08-09/KLMG019/UGC-SWRO.
E-mail address: indulalgopal@yahoo.com (Gopalapillai Indulal)
Copyright c© 2009 DMFA
94 Ars Math. Contemp. 2 (2009) 93–100
computationally a much more intense problem and, in general, there are no simple analyti-
cal solutions except for a few trees [6]. For this reason, distance polynomials of only trees
have been studied extensively in the mathematical literature [6, 16].
The distance matrix of a graph has numerous applications to chemistry and other bran-
ches of science. The distance matrix, contains information on various walks and self-
avoiding walks of chemical graphs, is immensely useful in the computation of topological
indices such as the Wiener index, is useful in the computation of thermodynamic properties
such as pressure and temperature coefficients and it contains more structural information
compared to a simple adjacency matrix. In addition to such applications in chemical sci-
ences, distance matrices find applications in music theory, ornithology, molecular biology,
psychology, archeology etc. For a survey see [1] and also the papers cited therein.
Let G be a connected graph with vertex set V (G) = {u1, u2, . . . , . . . , up}. The distance
matrixD = D(G) ofG is defined so that its (i, j)-entry is equal to dG(ui, uj), the distance
(= length of the shortest path [2]) between the vertices ui and uj of G. The eigenvalues
of D(G) are said to be the D-eigenvalues of G and form the distance spectrum or the
D-spectrum of G , denoted by specD(G).
The characteristic polynomial of theD-matrix and the corresponding spectra have been
considered in [4, 6, 7, 8]. For some recent works on D-spectrum see [9, 10, 11, 12, 13, 18].
For two graphs, the ordinary spectrum of graph compositions is well explored and
generalized results of NEPS of graphs are presented in [3]. Such studies for the distance
spectrum did not appear in literature yet and hence in this paper we present the following.
Let G and H be two graphs. Let G + H and G[H] denote the cartesian product and
lexicographic product of G and H respectively [3].
In this paper we first derive the D-spectrum of G + H and G[H]. By means of this,
the distance spectrum of the Hamming graph and C4 nanotori are obtained. A work of this
type is reported here for the first time.
All graphs considered in this paper are simple and we follow [3] for spectral graph
theoretic terminology and [2] for distance in graphs. The considerations in the subsequent
sections are based on the applications of the following lemmas.
Lemma 1.1 ([3]). Let G be an r-regular graph on p vertices with adjacency eigenvalues
r, λ2, . . . , λp. Then G and its complement G have the same eigenvectors, and the eigenval-
ues of G are p− r − 1,−1− λ2, . . . ,−1− λp.
Lemma 1.2 ([5]). The distance spectrum of the cycle Cn is given by
n greatest eigenvalue j even j odd
even
n2
4
0 − cosec2
(
πj
n
)
odd
n2 − 1
4
−1
4
sec2
(
πj
2n
)
−1
4
cosec2
(
πj
2n
)
G. Indulal: Distance spectrum of graph compositions 95
Definition 1.3 ([14]). The Hamming graph Ham(d, n), d ≥ 2, n ≥ 2, of diameter d
and characteristic n have vertex set consisting of all d-tuples of elements taken from an n-
element set, with two vertices adjacent if and only if they differ in exactly one coordinate.
Ham(d, n) is equal to Kn +Kn + · · ·+Kn︸ ︷︷ ︸
d
, the cartesian product of Kn, the complete
graph on n vertices, d times. Ham(3, n) is referred to as a cubic lattice graph.
Lemma 1.4 ([17]). Let G and H be two connected graphs, and let u = (u1, u2), v =
(v1, v2) ∈ V (G)× V (H). Let G+H denote their cartesian product. Then
dG+H(u, v) = dG(u1, v1) + dH(u2, v2).
2 The D-spectrum of G + H
In this section we derive the D-spectrum of the cartesian product of two distance regular
graphs.
Theorem 2.1. Let G and H be two distance regular graphs on p and n vertices with dis-
tance regularity k and t respectively. Let specD(G) = {k, µ2, µ3, . . . , µp} and specD(H)
= {t, η2, η3, . . . , ηn}. Then
specD(G+H) = {nk + pt, nµi, pηj , 0}
i = 2, . . . , p , j = 2, . . . , n and 0 is with multiplicity (p− 1)(n− 1).
Proof. Let DG and DH be the distance matrices of G and H respectively. Let V (G) =
{u1, u2, . . . , up} and V (H) = {v1, v2, . . . , vn}. Then DG = [dij ] and DH = [eij ] where
dij = dG(ui, uj) and eij = dH(vi, vj). Since G and H are distance regular graphs with
distance regularities k and t respectively, we have
p∑
j=1
drj = k and
n∑
j=1
eqj = t (2.1)
Also since G is distance regular, the all one column vector of order p × 1 is the eigen-
vector corresponding to the greatest eigenvalue k of DG. As DG is real and symmetric,
it is diagonalizable and hence admits an orthogonal basis BG consisting of eigenvectors
corresponding to its eigenvalues. Thus if µi is an eigenvalue of DG which is different from
k with an eigenvector Xi =
[
x1i , x
2
i , . . . , x
p
i
]T ∈ BG, then p∑
j=1
xji = 0.
Let u = (u1, u2), v = (v1, v2) ∈ V (G)× V (H). Then by Lemma 1.4
dG+H(u, v) = dG(u1, v1) + dH(u2, v2).
By a suitable ordering of vertices in G+H and by virtue of Lemma 1.4, its D-matrix,
C can be written in the form
96 Ars Math. Contemp. 2 (2009) 93–100
C =

d11 + e11 · · · d11 + e1n · · · · · · d1p + e11 · · · d1p + e1n
...
...
...
...
...
...
...
...
d11 + en1 · · · d11 + enn · · · · · · d1p + en1 · · · d1p + enn
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
dp1 + e11 · · · dp1 + e1n · · · · · · dpp + e11 · · · dpp + e1n
...
...
...
...
...
...
...
...
dp1 + e1n
... dp1 + enn · · · · · · dpp + en1 · · · dpp + enn

=

d (u1, u1) · Jn +DH d (u1, u2) · Jn +DH · · · · · · d (u1, up) · Jn +DH
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
d (up, u1) · Jn +DH d (up, u2) · Jn +DH · · · · · · d (up, up) · Jn +DH

= DG ⊗ Jn + Jp ⊗DH
where ⊗ denotes the tensor product of matrices.
Now we find the eigenvalues of C by considering eigenvectors associated with them. The
following relation for matrices is well known [15]. For the matrices A,B,C and D
(A⊗B) · (C ⊗D) = (AC)⊗ (BD)
whenever the products AC and BD exist.
Let 1G denote the all one eigenvector corresponding to the eigenvalue k of G and 1H
the all one eigenvector corresponding to the eigenvalue t of H . Then
DG · 1G = k1G and DH · 1H = t1H
Therefore
C · (1G ⊗ 1H) = (DG ⊗ Jn + Jp ⊗DH) · (1G ⊗ 1H)
= (DG · 1G)⊗ (Jn1H) + (Jp1G)⊗ (DH · 1H)
= k1G ⊗ n1H + p1G ⊗ t1H
= nk · (1G ⊗ 1H) + pt · (1G ⊗ 1H)
= (nk + pt) · (1G ⊗ 1H)
showing that 1G ⊗ 1H is the eigenvector corresponding to the eigenvalue nk + pt of C.
Let Xi be the eigenvector corresponding to the eigenvalue µi of DG. Then Xi ⊗ 1H is
the eigenvector corresponding to the eigenvalue nµi of C. For
C · (Xi ⊗ 1H) = (DG ⊗ Jn + Jp ⊗DH) · (Xi ⊗ 1H)
= (DG ·Xi)⊗ (Jn1H) + (JpXi)⊗ (DH · 1H)
= µiXi ⊗ n1H + 0⊗ t1H
= nµi (Xi ⊗ 1H)
G. Indulal: Distance spectrum of graph compositions 97
Similarly if Zj is an eigenvector corresponding to the eigenvalue ηj of DH , then 1G ⊗
Zj is an eigenvector corresponding to the eigenvalue pηj of C.
In addition to these eigenvalues we can see that 0 appears to be an eigenvalue with
multiplicity (p− 1)(n− 1). For let Rip, i = 2, 3, . . . , p be the (p− 1) linearly independent
eigenvectors corresponding to the eigenvalue 0 of Jp and T jn, j = 2, 3, . . . , n − 1 be the
(n − 1) linearly independent eigenvectors corresponding to the eigenvalue 0 of Jn. Then
the (p − 1)(n − 1) vectors Rip ⊗ T jn are linearly independent and are the eigenvectors
corresponding to 0 of C. For
C ·
(
Rip ⊗ T jn
)
= (DG ⊗ Jn + Jp ⊗DH) ·
(
Rip ⊗ T jn
)
=
(
DG ·Rip
)
⊗
(
Jn · T jn
)
+
(
JpR
i
p
)
⊗
(
DH · T jn
)
=
(
DG ·Rip
)
⊗ 0 + 0⊗
(
DH · T jn
)
= 0
Now the pn vectors Xi ⊗ 1H , 1G ⊗Zj and Rip ⊗ T jn are linearly independent and as C
has a basis consisting of linearly independent eigenvectors, the theorem follows.
2.1 The D-spectrum of Ham(d, n)
In [14], the ordinary spectrum of the cubic lattice graph is obtained. In this section we use
Theorem 2.1 to obtain the D-spectrum of Ham(d, n).
Theorem 2.2. Let Ham(d, n) be the Hamming graph of characteristic n. Then the D-
eigenvalues of Ham(d, n) are dnd−1 (n− 1), 0 and −nd−1 with multiplicities 1, nd −
d(n− 1)− 1 and d (n− 1) respectively.
Proof. The graph Kn is distance regular with distance regularity n − 1. Now the proof
follows by repeated application of Theorem 2.1 and from the ordinary spectrum of Kn
[3].
2.2 The D-spectrum of the C4 nanotori, Tk,m,C4
The graph Ck + Cm where both k and m are odd is defined as the C4 nanotori, Tk,m,C4 .
Theorem 2.3. The distance spectrum of the C4 nanotori, Tk,m,C4 consists of the following
numbers
(m+ k) (mk − 1)
4
, −m
4
sec2
(
πj
2k
)
, −m
4
cosec2
(πr
2k
)
,
−k
4
sec2
(
πt
2m
)
, −k
4
cosec2
(
πl
2m
)
where j ∈ {1, 2, . . . , k−1} and even, r ∈ {1, 2, . . . , k−1} and odd t ∈ {1, 2, . . . ,m−1}
and even and l ∈ {1, 2, . . . ,m−1} and odd together with 0 of multiplicity (m−1)(k−1).
Proof. The cycle C2n+1 is distance regular with distance regularity n(n + 1). Now the
proof follows from Theorem 2.1 and Lemma 1.2.
98 Ars Math. Contemp. 2 (2009) 93–100
3 The D-spectrum of G[H]
In this section we obtain the distance spectrum of the lexicographic product G[H] of two
graphs G and H . The following definition of the lexicographic product of G and H is from
[3].
Definition 3.1. Let G and H be two graphs on vertex sets V (G) = {u1, u2, . . . , . . . , up}
and V (H) = {v1, v2, . . . , . . . , vn} respectively. Then their lexicographic product G[H] is
a graph defined by V (G[H]) = V (G)× V (H), the cartesian product of V (G) and V (H)
in which u = (u1, v1) be adjacent to v = (u2, v2) if and only if either
1. u1 be adjacent to v1 in G or
2. u1 = v1 and u2 be adjacent to v2 in G.
Distance in G[H]
We prove the following lemma on distance in lexicographic product of graphs.
Lemma 3.2. Let G and H be two connected graphs with atleast two vertices and let u =
(u1, v1), v = (u2, v2) ∈ V (G)× V (H). Then
dG[H](u, v) =

dG(u1, u2) if u1 6= u2
1 if u1 = u2 and v1 adjacent to v2
2 if u1 = u2 and v1 not adjacent to v2
Proof. We show that in the corresponding composition there exist a path between u and v
of length as given in the lemma. Let dG(u1, u2) = t and u1 = s0, s1, . . . , st = u2 be the
shortest u1 − u2 path in G.
Let u = (u1, v1), v = (u2, v2) ∈ V (G) × V (H) and u1 6= u2. Since the successive
ordered pairs in any u− v path can change both the coordinates and also as u2 is reachable
from u1 by not less that t steps, any u− v path in G[H] is of length atleast t.
Now the following u− v path in G[H] is of length t.
P : u = (s0, v1), (s1, v2), (s2, v2), . . . , (st, v2) = v. Thus dG[H](u, v) = dG(u1, u2)
if u1 6= u2.
Now suppose u1 = u2 and v1 be adjacent to v2. Then by the definition of G[H], we
have dG[H](u, v) = 1.
Now suppose u1 = u2 and v1 is not adjacent to v2. Let s1 be adjacent to u1 in G. Then
u is not adjacent to v and u = (u1, v1), (s1, v2), (u1, v2) = v is a u − v path of length 2.
Thus dG[H](u, v) = 2. Hence the Lemma.
Theorem 3.3. Let G be a graph with D-matrix DG and H , an r-regular graph with an
adjacency matrix A. Let specD(G) = {µ1, µ2, . . . , µp} and the ordinary spectrum of H
be {r, λ2, λ3, . . . , λn}. Then
specDG[H] =
(
nµi + 2n− r − 2 − (λj + 2)
1 p
)
, i = 1 to p and j = 2 to n− 1
G. Indulal: Distance spectrum of graph compositions 99
Proof. Using Lemma 3.2 and by a suitable ordering of vertices of G[H], its D-matrix F ,
can be written in the form
F =

d12 · · · d12 d13 · · · d13 · · · · · · d1p
A+ 2A
...
...
...
...
...
...
...
...
...
d12 d12 d12 d13 · · · d13 · · · · · · d1p
d21 · · · d21 · · · · · · · · · d2p · · · d2p
...
...
... A+ 2A
...
...
...
d21 · · · d21 d2p · · · d2p
...
...
...
...
...
. . .
...
...
...
...
...
...
dp1 · · · dp1 · · · · · · · · ·
. . . · · · · · ·
...
...
...
...
...
...
...
...
...
... A+ 2A
dp1 · · · dp1 · · · · · · · · · · · · · · · · · · · · ·

= DG ⊗ Jn + Ip ⊗ (A+ 2A )
where A denote the adjacency matrix of G.
Since H is r-regular, the all one column vector 1 of order n× 1 is an eigenvector of A
with an eigenvalue r. Then by Lemma 1.1, the all one vector 1 is an eigenvector of A+2A
with an eigenvalue 2n−r−2. Similarly if λj is any other eigenvalue ofA with eigenvector
Yj , then Yj is an eigenvector ofA+2Awith eigenvalue−(λj +2) and that Yj is orthogonal
to 1.
Let Xi =
[
xi1 x
i
2 . . . x
i
p
]T
be an eigenvector corresponding to the eigenvalue µi
of DG. Therefore
DG ·Xi = µiXi
Now
F · (Xi ⊗ 1n) =
(
DG ⊗ Jn + Ip ⊗
(
A+ 2A
))
(Xi ⊗ 1n)
= (DG ·Xi)⊗ (Jn · 1n) + (Ip ·Xi)⊗
(
A+ 2A
)
· 1n
= µiXi ⊗ n1n +Xi ⊗ (2n− r − 2) 1n
= nµi (Xi ⊗ 1n) + (2n− r − 2) (Xi ⊗ 1n)
= (nµi + 2n− r − 2) (Xi ⊗ 1n)
Therefore nµi + 2n− r − 2 is an eigenvalue of F with eigenvector Xi ⊗ 1n.
As Yj is orthogonal to 1, we have Jn · Yj = 0 for each j = 2, 3, . . . , n.
Let {Zk} , k = 1, 2, . . . , p be the family of p linearly independent eigenvectors associ-
ated with the eigenvalue 1 of Ip. Then for each j = 2, 3, . . . , n, the p vectors Zk ⊗ Yj are
eigenvectors of F with eigenvalue −(λj + 2). For
F · (Zk ⊗ Yj) =
(
DG ⊗ Jn + Ip ⊗
(
A+ 2A
))
(Zk ⊗ Yj)
= (DG · Zk)⊗ (Jn · Yj) + (Ip · Zk)⊗
(
A+ 2A
)
· Yj
= 0 + Zk ⊗− (λj + 2)Yj
= − (λj + 2) · (Zk ⊗ Yj)
100 Ars Math. Contemp. 2 (2009) 93–100
Also the pn vectors Xi ⊗ 1n and Zk ⊗ Yj are linearly independent. As the eigenvectors
belonging to different eigenvalues are linearly independent and as F has a basis consisting
entirely of eigenvectors, the theorem follows.
Acknowledgements
The author is indebted to the anonymous referees for their valuable comments and sugges-
tions which led to an improved presentation of the results.
References
[1] K. Balasubramanian, Computer Generation of Distance Polynomials of Graphs, Journal of
Computational Chemistry 11 (1990), 829–836.
[2] F. Buckley and F. Harary, Distance in Graphs, Addison Wesley, 1990.
[3] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs. Theory and Applications, Aca-
demic Press, New York – London, 1980.
[4] M. Edelberg, M. R. Garey and R. L. Graham, On the distance matrix of a tree, Discrete Math.
14 (1976), 230–39.
[5] P. W. Fowler, G. Caporossi and P. Hansen, Distance matrices, Wiener indices, and related
invariants of fullerenes, J. Phys. Chem. A. 105 (2001), 6232–6242.
[6] R. L. Graham and L. Lovasz, Distance matrix polynomials of trees, Adv. Math. 29 (1978),
60–88.
[7] R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System
Tech. J. 50 (1971), 2495–2519.
[8] R. L. Graham and H. O. Pollak, On embedding graphs in squashed cubes, in: Y. Alavi, D. R.
Lick and A. T. White (eds.), Graph theory and applications (Lecture notes in Mathematics,
vol. 303), Springer, Berlin, 1972, 99–110.
[9] G. Indulal, I. Gutman and A. Vijayakumar, On distance energy of graphs, MATCH Commun.
Math. Comput. Chem. 60 (2008), 461–472.
[10] G. Indulal and I. Gutman, On the distance spectra of some graphs, Math. Commun. 13 (2008),
123–131.
[11] G. Indulal and I. Gutman, D-equienergetic self-complementary graphs, Kragujevac J. Math.,
in press.
[12] G. Indulal, D-spectra and D-energy of the complements of iterated line graphs of regular
graphs, communicated.
[13] G. Indulal, Sharp bounds on the distance spectral radius and the distance energy of graphs, Lin.
Algebra Appl. 430 (2009), 106–113.
[14] R. Laskar, Eigenvalues of the adjacency matrix of cubic lattice graphs, Pacific J. Math. 29
(1969), 623–629.
[15] M. Marcus and H. Mine, A survey of Matrix theory and Matrix inequalities, Allyn and Bacon,
Inc., Boston, Mass., 1964.
[16] B. D. McKay, On the spectral characterization of trees, Ars Combin. 3 (1977), 219–232.
[17] D. Stevanović, Distance Regularity of Compositions of Graphs, Appl. Math. Lett. 17 (2004),
337–343.
[18] D. Stevanović and G. Indulal, The distance spectrum and energy of the compositions of regular
graphs, Appl. Math. Lett. 22 (2009), 1136–1140.