×

Edge-disjoint spanners of complete graphs and complete digraphs. (English) Zbl 0932.05028

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\).

MSC:

05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Althöfer, I.; Das, G.; Dobkin, D.; Joseph, D.; Soares, J., On sparse spanners of weighted graphs, Discrete Comput. Geom., 9, 81-100 (1993) · Zbl 0762.05039
[2] B. Awerbuch, A. Baratz, D. Peleg, Efficient broadcast and light-weight spanners, Technical Report CS92-22, the Weizmann Institute of Science, Rehovot, Israel, 1992.; B. Awerbuch, A. Baratz, D. Peleg, Efficient broadcast and light-weight spanners, Technical Report CS92-22, the Weizmann Institute of Science, Rehovot, Israel, 1992.
[3] Awerbuch, B.; Berger, B.; Cowen, L.; Peleg, D., Near-linear time construction of sparse neighborhood covers, SIAM J. Comput., 28, 263-277 (1998) · Zbl 0943.05079
[4] B. Awerbuch, D. Peleg, Sparse partitions, 31st IEEE Symposium on Foundations of Computer Science, 1990, pp. 503-513.; B. Awerbuch, D. Peleg, Sparse partitions, 31st IEEE Symposium on Foundations of Computer Science, 1990, pp. 503-513.
[5] B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978, p. 216.; B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978, p. 216.
[6] Bosák, J., Disjoint factors of diameter two in complete graphs, J. Combin. Theory, Ser. B, 16, 57-63 (1974) · Zbl 0256.05117
[7] J. Bosák, A. Rosa, Š. Znám, On decompositions of complete graphs into factors with given diameters, in: P. Erdös, G. Katona (Eds.), Theory of Graphs, Proceedings of Colloq. Tihany, 1966, Academic Press, New York and Academy Kiadó, Budapest, 1968, pp. 37-56.; J. Bosák, A. Rosa, Š. Znám, On decompositions of complete graphs into factors with given diameters, in: P. Erdös, G. Katona (Eds.), Theory of Graphs, Proceedings of Colloq. Tihany, 1966, Academic Press, New York and Academy Kiadó, Budapest, 1968, pp. 37-56.
[8] Cai, L., NP-completeness of minimum spanner problems, Discrete Appl. Math., 48, 187-194 (1994) · Zbl 0788.68057
[9] Cai, L.; Corneil, D., Isomorphic tree spanner problems, Algorithmica, 14, 138-153 (1995) · Zbl 0833.68091
[10] Cai, L.; Corneil, D., Tree spanners, SIAM J. Discrete Math., 8, 359-387 (1995) · Zbl 0832.05037
[11] Cai, L.; Keil, M., Spanners in graphs of bounded degree, Networks, 24, 233-249 (1994) · Zbl 0821.68091
[12] B. Chandra, G. Das, G. Narasimhan, J. Soares, New sparseness results on graph spanners, Proceedings of eighth ACM Symposium on Computational Geometry, 1992.; B. Chandra, G. Das, G. Narasimhan, J. Soares, New sparseness results on graph spanners, Proceedings of eighth ACM Symposium on Computational Geometry, 1992. · Zbl 0818.68078
[13] E. Cohen, Fast algorithms for constructing \(tt\); E. Cohen, Fast algorithms for constructing \(tt\)
[14] D. Dor, S. Halperin, U. Zwick, All pairs almost shortest paths, Proceedings of 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 452-461.; D. Dor, S. Halperin, U. Zwick, All pairs almost shortest paths, Proceedings of 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 452-461. · Zbl 0948.05047
[15] Goldberg, M. K., The diameter of a strongly connected graph (in Russian), Dokl. AN SSR, 170, 767-769 (1966)
[16] R. Harbane, C. Padro, Spanners of underlying graphs of iterated line digraphs, Proceedings of third Colloqium on Structural Information & Communication Complexity, Carleton Univ. Press, 1996.; R. Harbane, C. Padro, Spanners of underlying graphs of iterated line digraphs, Proceedings of third Colloqium on Structural Information & Communication Complexity, Carleton Univ. Press, 1996. · Zbl 1337.68208
[17] Heydemann, M.-C.; Peters, J.; Sotteau, D., Spanners of hypercube-derived networks, SIAM J. Discrete Math., 9, 37-54 (1966) · Zbl 0841.68008
[18] Kortsarz, G.; Peleg, D., Generating sparse 2-spanners, J. Algorithms, 17, 222-236 (1994) · Zbl 1427.68246
[19] Kortsarz, G.; Peleg, D., Generating low-degree 2-spanners, SIAM J. Comput., 27, 1438-1456 (1998) · Zbl 0909.05023
[20] C. Laforest, A.L. Liestman, T.C. Shermer, D. Sotteau, Edge disjoint graph spanners of complete graphs and complete digraphs (extended abstract), Proceedings of 30th Hawaii International Conference on System Sciences, vol. I, 1997, pp. 191-199.; C. Laforest, A.L. Liestman, T.C. Shermer, D. Sotteau, Edge disjoint graph spanners of complete graphs and complete digraphs (extended abstract), Proceedings of 30th Hawaii International Conference on System Sciences, vol. I, 1997, pp. 191-199. · Zbl 0982.05058
[21] Liestman, A. L.; Shermer, T. C., Additive spanners for hypercubes, Par. Proc. Lett., 1, 35-42 (1991)
[22] Liestman, A. L.; Shermer, T. C., Grid spanners, Networks, 23, 123-133 (1993) · Zbl 0777.05077
[23] Liestman, A. L.; Shermer, T. C., Additive graph spanners, Networks, 23, 343-364 (1993) · Zbl 0783.68094
[24] Liestman, A. L.; Shermer, T. C., Degree-constrained network spanners with non-constant delay, SIAM J. Discrete Math., 8, 291-321 (1995) · Zbl 0939.68529
[25] Liestman, A. L.; Shermer, T. C.; Stolte, C. R., Degree-constrained spanners for multi-dimensional grids, Discrete Appl. Math., 68, 119-144 (1996) · Zbl 0852.05041
[26] D.E. Lucas, Récréations Mathématiques, vol. II, Gauthier Villars, Paris, 1892.; D.E. Lucas, Récréations Mathématiques, vol. II, Gauthier Villars, Paris, 1892.
[27] Y. Mansour, D. Peleg, An approximation algorithm for minimum-cost network design, Technical Report CS94-22, the Weizmann Institute of Science, 1994.; Y. Mansour, D. Peleg, An approximation algorithm for minimum-cost network design, Technical Report CS94-22, the Weizmann Institute of Science, 1994. · Zbl 0963.68231
[28] I. Niven, H.S. Zuckerman, An Introduction to the Theory of Numbers, fourth ed., Wiley, New York, 1980, p. 42.; I. Niven, H.S. Zuckerman, An Introduction to the Theory of Numbers, fourth ed., Wiley, New York, 1980, p. 42. · Zbl 0431.10001
[29] Peleg, D.; Schäffer, A. A., Graph spanners, J. Graph Theory, 13, 99-116 (1989) · Zbl 0673.05059
[30] Peleg, D.; Ullman, J. D., An optimal synchronizer for the hypercube, SIAM J. Comput., 18, 740-747 (1989) · Zbl 0681.68091
[31] Richards, D.; Liestman, A. L., Degree-constrained pyramid spanners, J. Partial Distr. Comput., 25, 1-6 (1995)
[32] Stacho, L.; Urland, E., The nonexistence of a decomposition of complete graph \(K_{12}\) into three factors with diameter two, J. Combin. Math. Combin. Comput., 21, 147-159 (1996) · Zbl 0861.05048
[33] Tillson, T., A Hamiltonian decomposition of \(K_{2n}*, 2n\) ⩾ 8, J. Combin. Theory Ser. B, 29, 68-74 (1980) · Zbl 0439.05025
[34] Tomová, E., On the decomposition of the complete directed graph into factors with given diameters, Mat. Čas., 20, 257-261 (1970) · Zbl 0205.28504
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.