Edge-disjoint spanners of complete graphs and complete digraphs (Q1301660)

A spanning subgraph \(S\) of a connected graph (or directed graph) \(G\) is an \(f(x)\)-spanner if, for any pair of vertices \(u\) and \(v\), \(d_S(u,v) \leq f(d_G(u,v))\), where \(d_G\) and \(d_S\) are the distance functions in the graphs (digraphs) \(G\) and \(S\). For appropriate constants \(c\), the authors investigate the maximum number \(\text{EDS} (G,c)\) of edge-disjoint \((x+c)\)-spanners of the complete graph on \(n\) vertices \(G = K_n\), respectively, of the complete directed graph on \(n\) vertices \(G = K_n^*\) that can be formed from \(K_n\) by replacing every edge with two oppositely directed edges. Among others, they prove that (i) \(\text{EDS} (K_n,c) = \lfloor \frac{n}{2} \rfloor\) for \(n \geq 4\), \(2 \leq c \leq n-2\), and \(\text{EDS} (K_n,1) \approx \frac{n}{6}\) for large \(n\), (ii) \(\lfloor \frac{n}{2}\rfloor \leq \text{EDS} (K_n^*,c) \leq \lfloor \frac{n^2-n}{n+\lfloor \frac{2n-3}{c+1} \rfloor} \rfloor\) for \(n \geq 7\), \(3 \leq c \leq n-4\), (iii) \(\text{EDS} (K_n^*,2) = \lfloor \frac{n}{2} \rfloor\), and \(\lfloor \frac{n}{4} \rfloor \leq \text{EDS} (K_n^*,1) \leq \lceil \frac{n}{4} \rceil\) for \(n \geq 5\).