Name
Abstract | ||
|---|---|---|
Let G be a connected graph and T be a spanning tree of G. For e@?E(T), the congestion of e is the number of edges in G connecting two components of T-e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2008.12.021 | Discrete Mathematics |
Keywords | Field | DocType |
complete k-partite graph,complete k -partite graph,edge isoperimetric problem,torus,spanning tree congestion,spanning tree,lower bound,connected graph,isoperimetric problem | Discrete mathematics,Combinatorics,Minimum degree spanning tree,k-minimum spanning tree,Euclidean minimum spanning tree,Connected dominating set,Spanning tree,Shortest-path tree,Mathematics,Kruskal's algorithm,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
309 | 13 | Discrete Mathematics |
Citations | PageRank | References |
7 | 0.58 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kyohei Kozawa | 1 | 23 | 3.21 |
| Yota Otachi | 2 | 161 | 37.16 |
| Koichi Yamazaki | 3 | 222 | 21.85 |