Edge-disjoint spanners of complete bipartite graphs (Q5936052): Difference between revisions

An \((x+c)\)-spanner of a connected graph \(G=(V,E)\) is a spanning subgraph such that for all vertices \(v,w\in V\), the distance between \(v\) and \(w\) in \(G\) and in the spanner differ by at most \(c\). \(c\) is called the delay of the spanner. This paper looks to the number of edge-disjoint spanners in complete bipartite graphs \(K_{n,m}\) of a specified delay. For all values of \(n\) and \(m\) and all delays at least four, this number is exactly determined. For delay two, for many cases of \(n\) and \(m\), an exact bound is given; for other cases, upper and lower bounds are given.