×

On spanning tree congestion. (English) Zbl 1213.05093

Summary: We prove that every connected graph \(G\) of order \(n\) has a spanning tree \(T\) such that for every edge \(e\) of \(T\) the edge cut defined in \(G\) by the vertex sets of the two components of \(T - e\) contains at most \(n^{\frac 3 2}\) edges. This result solves a problem posed by M.I. Ostrovskii [“Minimal congestion trees,” Discrete Math. 285, No.1-3, 219–226 (2004; Zbl 1051.05032).

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1051.05032
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bezrukov, S. L.; Chavez, J. D.; Harper, L. H.; Röttger, M.; Schroeder, U.-P., The congestion of \(n\)-cube layout on a rectangular grid, Discrete Math., 213, 13-19 (2000) · Zbl 0953.68115
[2] Bienstock, D., On embedding graphs in trees, J. Combin. Theory Ser. B., 49, 103-136 (1990) · Zbl 0646.05025
[3] Chavez, J. D.; Trapp, R., The cyclic cutwidth of trees, Discrete Appl. Math., 87, 25-32 (1998) · Zbl 0909.05024
[4] Chung, F. R.K., Labelings of graphs, (Selected Topics in Graph Theory, vol. 3 (1988), Academic Press: Academic Press San Diego), 151-168 · Zbl 0656.05058
[5] Gomory, R. E.; Hu, T. C., Multi-terminal network flows, J. SIAM, 9, 551-570 (1961) · Zbl 0112.12405
[6] Győri, E., On division of graphs to connected subgraphs, (Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol I. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol I, Colloq. Math. Soc. János Bolyai, vol. 18 (1978), North-Holland: North-Holland Amsterdam, New York), 485-494 · Zbl 0388.05008
[7] Hruska, S. W., On tree congestion of graphs, Discrete Math., 308, 1801-1809 (2008) · Zbl 1151.05014
[8] Lovász, L., A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar., 30, 241-251 (1977) · Zbl 0403.05040
[9] Mohar, B., Isoperimetric numbers of graphs, J. Combin. Theory Ser. B, 47, 274-291 (1989) · Zbl 0719.05042
[10] Ostrovskii, M. I., Minimal congestion trees, Discrete Math., 285, 219-226 (2004) · Zbl 1051.05032
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.