CLIQUE DECOMPOSITIONS OF THE DISTANCE MULTIGRAPH OF THE CARTESIAN PRODUCT OF GRAPHS

Abstract

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