Edge-disjoint spanners in Cartesian products of graphs Original Research Article

A spanning subgraph image of a connected graph image is an image-spanner if for any pair of vertices u and v, image where image and image 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.