|
|||||
 |
|
|
|
|
|
Spanning tree
congestion of planar graphs
Hiu Fai Law, Siu Lam Leung and Mikhail I. Ostrovskii
Vol. 7 (2014), No. 2, 205–226
|
Abstract |
|
This paper is devoted to estimates of the spanning tree congestion for some planar graphs. We present three main results: (1) We almost determined (up to ) the maximal possible spanning tree congestion for planar graphs. (2) The value of congestion indicator introduced by Ostrovskii [Discrete Math. 310, 1204–1209] can be very far from the value of the spanning tree congestion. (3) We find some more examples in which the congestion indicator can be used to find the exact value of the spanning tree congestion. |
Keywords
dual graph, dual spanning tree, minimum congestion spanning
tree, planar graph
|
Mathematical Subject Classification 2010
Primary: 05C05
Secondary: 05C10, 05C35
|
Milestones
Received: 19 March 2013
Revised: 2 July 2013
Accepted: 3 July 2013
Published: 16 November 2013
Communicated by Joseph A. Gallian
|
Authors |
| Hiu Fai Law | |
| Department of Mathematics Universität Hamburg 55 Bunderstrasse D-20146 Hamburg Germany |
|
| Siu Lam Leung | |
| Department of Mathematics and
Computer Science St. John’s University 8000 Utopia Parkway Queens, NY 11439 United States |
|
| Mikhail I. Ostrovskii | |
| Department of Mathematics and
Computer Science St. John’s University 8000 Utopia Parkway Queens, NY 11439 United States |
|
|
