Minimal congestion trees (Q1877665): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:01, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimal congestion trees |
scientific article |
Statements
Minimal congestion trees (English)
0 references
19 August 2004
0 references
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.
0 references
minimal congestion spanning tree
0 references
Cheeger constant
0 references
isoperimetric dimension
0 references