Edge-disjoint spanners in Cartesian products of graphs

Abstract: A spanning subgraph of a connected graph is an -spanner if for any pair of vertices u and v, where and are the usual distance functions in G and S, respectively. The parameter c is called the delay of the spanner. We study edge-disjoint spanners in graphs, focusing on graphs formed as Cartesian products. Our approach is to construct sets of edge-disjoint spanners in a product based on sets of edge-disjoint spanners and colorings of the component graphs. We present several results on general products and then narrow our focus to hypercubes. [Copyright &y& Elsevier]