CLIQUE DECOMPOSITIONS OF THEDISTANCE MULTIGRAPH OF THECARTESIAN PRODUCT OF GRAPHS

Abstract

The distance multigraph of a graph
G
is the multigraph having the
same vertex set as
G
with
d
G
(
u,v
) edges connecting each pair of vertices
u
and
v
,where
d
G
(
u,v
) is the distance between vertices
u
and
v
in
G
.
In this paper, we introduce a technique to construct a clique decomposi-
tion of the distance multigraph of the
Cartesian product of two arbitrary
graphs. Such a construction is accomplished through using clique de-
compostions of the distance multigraphs of the component graphs and
mutually orthogonal Latin squares.