×

Minimal congestion trees. (English) Zbl 1051.05032

For graphs \(H\) and \(G\), an \(H\)-layout \(L\) of \(G\) assigns to each edge in \(G\) a path in \(H\). The congestion of the layout is the maximum over all edges \(e\) in \(H\) of the number of paths that use \(e\). The {tree congestion} of a graph \(G\) is the minimum congestion over all \(T\)-layouts over all trees \(T\) with the same vertex set as \(G\); the {spanning tree congestion} is obtained when we additionally require \(T\) to be a spanning tree of \(G\).
This paper gives a number of estimates for the tree congestion and spanning tree congestion. It is shown that the tree and spanning tree congestion of \(G=(V,E)\) is at most \(| E| -| V| +2\). Lower bounds on the spanning tree congestions in terms of the {isoperimetric dimension} and the {Cheeger constant} are also given. A \(k\)-regular graph is shown to have tree congestion \(k\). Also, several bounds are derived on the maximum possible spanning tree congestion that can be attained on a graph with \(n\) vertices.

MSC:

05C05 Trees
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bezrukov, S. L.; Chavez, J. D.; Harper, L. H.; Röttger, M.; Schoeder, U.-P, The congestion of \(n\)-cube layout on a rectangular grid, Discrete Math., 213, 13-19 (2000) · Zbl 0953.68115
[2] Bhutani, K. R.; Khan, B., The metric space of connected simple graphs, Aequationes Math., 66, 232-240 (2003) · Zbl 1066.05052
[3] Bienstock, D., On embedding graphs in trees, J. Combin. Theory Ser. B, 49, 1, 103-136 (1990) · Zbl 0646.05025
[4] Bollobás, B., Modern Graph Theory (1998), Springer: Springer New York · Zbl 0902.05016
[5] Boruvka, O., O jistém problému minimálnim, Práce Moravské Přidovědecké Spolecnosti v Brně, III, 3, 37-58 (1926), (Czech, German summary)
[6] Chavez, J. D.; Trapp, R., The cyclic cutwidth of trees, Discrete Appl. Math., 87, 25-32 (1998) · Zbl 0909.05024
[7] Chung, F. R.K, On the cutwidth and the topological bandwidth of a tree, SIAM J. Algebraic Discrete Meth., 6, 268-277 (1985) · Zbl 0565.05019
[8] F.R.K. Chung, Labelings of graphs, in: L.W. Beineke, R.J. Wilson (Eds.), Selected Topics in Graph Theory, Vol. 3, Academic Press, London, 1988, pp. 151-168.; F.R.K. Chung, Labelings of graphs, in: L.W. Beineke, R.J. Wilson (Eds.), Selected Topics in Graph Theory, Vol. 3, Academic Press, London, 1988, pp. 151-168.
[9] Chung, F. R.K, Spectral Graph Theory (1997), AMS: AMS Providence, RI · Zbl 0872.05052
[10] Chung, F. R.K; Seymour, P. D., Graphs with small bandwidth and cutwidth, Discrete Math., 75, 113-119 (1989) · Zbl 0668.05039
[11] Chung, F. R.K; Yau, S.-T, Eigenvalues of graphs and Sobolev inequalities, Combin. Probab. Comput., 4, 11-26 (1995) · Zbl 0843.05073
[12] Garey, M. R.; Johnson, D. S., Computers and Intractability. A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co: W.H. Freeman and Co San Francisco · Zbl 0411.68039
[13] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA
[14] Jarnik, V., O jistém problému minimálnim, Práce Moravské Přidovědecké Spolecnosti v Brně, VI, 4, 57-63 (1930), (Czech)
[15] Jordan, C., Sur les assemblages de lignes, J. Reine Angew. Math., 70, 185-190 (1869) · JFM 02.0344.01
[16] Korte, B.; Nešetřil, J., Vojtěch Jarnik’s work in combinatorial optimization, Discrete Math., 235, 1-17 (2001) · Zbl 1024.01018
[17] Kruskal, J., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc., 7, 48-50 (1956) · Zbl 0070.18404
[18] Lubotzky, A., Discrete Groups, Expanding Graphs and Invariant Measures (1994), Birkhäuser: Birkhäuser Basel · Zbl 0826.22012
[19] Makedon, F.; Sudborough, I. H., On minimizing width in linear layouts, Discrete Appl. Math., 23, 243-265 (1989) · Zbl 0715.05012
[20] Nešetřil, J.; Milková, E.; Nešetřilová, H., Otakar Boruvka on minimum spanning tree problemtranslation of both the 1926 papers, comments, history, Discrete Math., 233, 3-36 (2001) · Zbl 0999.01019
[21] Ostrovskii, M. I., Minimal-volume shadows of cubes, J. Funct. Anal., 176, 2, 317-330 (2000) · Zbl 0968.46017
[22] Ostrovskii, M. I., Minimal-volume projections of cubes and totally unimodular matrices, Linear Algebra Appl., 364, 91-103 (2003) · Zbl 1025.52008
[23] Prim, R. C., The shortest connecting network and some generalizations, Bell Systems Tech. J., 36, 1389-1401 (1957)
[24] Rosenberg, A. L.; Heath, L. S., Graph Separators, with Applications (2001), Kluwer Academic/Plenum Publishers: Kluwer Academic/Plenum Publishers New York
[25] Yannakakis, M., A polynomial algorithm for the Min-Cut linear arrangements of trees, J. ACM, 32, 950-988 (1985) · Zbl 0633.68063
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.