Minimal congestion trees (Q1877665)

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.