Edge-disjoint spanners of complete graphs and complete digraphs
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\).
- A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
- Additive graph spanners
- All-Pairs Almost Shortest Paths
- An Optimal Synchronizer for the Hypercube
- Degree-Constrained Network Spanners with Nonconstant Delay
- Degree-constrained spanners for multidimensional grids
- Disjoint factors of diameter two in complete graphs
- Edge-disjoint spanners of complete bipartite graphs
- Generating Low-Degree 2-Spanners
- Generating Sparse 2-Spanners
- Graph spanners
- Grid spanners
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3670509 (Why is no real title available?)
- scientific article; zbMATH DE number 1532274 (Why is no real title available?)
- scientific article; zbMATH DE number 927056 (Why is no real title available?)
- scientific article; zbMATH DE number 3258080 (Why is no real title available?)
- scientific article; zbMATH DE number 3257169 (Why is no real title available?)
- scientific article; zbMATH DE number 3326393 (Why is no real title available?)
- Isomorphic tree spanner problems
- Near-Linear Time Construction of Sparse Neighborhood Covers
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- NP-completeness of minimum spanner problems
- On sparse spanners of weighted graphs
- Spanners in graphs of bounded degree
- Spanners of Hypercube-Derived Networks
- Spanners of underlying graphs of iterated line digraphs
- Tree Spanners
This page was built for publication: Edge-disjoint spanners of complete graphs and complete digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1301660)
