# Spanning tree congestion of rook's graphs

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 4, page 753-761
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topKyohei Kozawa, and Yota Otachi. "Spanning tree congestion of rook's graphs." Discussiones Mathematicae Graph Theory 31.4 (2011): 753-761. <http://eudml.org/doc/270973>.

@article{KyoheiKozawa2011,

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 joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.},

author = {Kyohei Kozawa, Yota Otachi},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {spanning tree congestion; Rook's graph; rook's graph},

language = {eng},

number = {4},

pages = {753-761},

title = {Spanning tree congestion of rook's graphs},

url = {http://eudml.org/doc/270973},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Kyohei Kozawa

AU - Yota Otachi

TI - Spanning tree congestion of rook's graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 4

SP - 753

EP - 761

AB - 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 joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

LA - eng

KW - spanning tree congestion; Rook's graph; rook's graph

UR - http://eudml.org/doc/270973

ER -

## References

top- [1] J. Balogh and D. Mubayi and A. Pluhár, On the edge-bandwidth of graph products, Theoret. Comput. Sci. 359 (2006) 43-57, doi: 10.1016/j.tcs.2006.01.046. Zbl1098.05070
- [2] A. Bekmetjev and G. Hurlbert, The pebbling threshold of the square of cliques, Discrete Math. 308 (2008) 4306-4314, doi: 10.1016/j.disc.2007.08.012. Zbl1152.05050
- [3] S.L. Bezrukov, Edge isoperimetric problems on graphs, in: L. Lovasz, A. Gyarfas, G.O.H. Katona, A. Recski and L. Szekely, eds, Graph Theory and Combinatorial Biology, 7 Bolyai Soc. Math. Stud. 157-197 Janos Bolyai Math. Soc. (Budapest, 1999). Zbl0927.05080
- [4] H.L. Bodlaender, K. Kozawa, T. Matsushima and Y. Otachi, Spanning Tree Congestion of k-outerplanar Graphs, in: WAAC 2010 (2010) 34-39. Zbl1223.05017
- [5] A. Castejón and M.I. Ostrovskii, Minimum congestion spanning trees of grids and discrete toruses, Discuss. Math. Graph Theory 29 (2009) 511-519, doi: 10.7151/dmgt.1461. Zbl1193.05058
- [6] M. Chudnovsky and N. Robertson and P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006) 51-229, doi: 10.4007/annals.2006.164.51. Zbl1112.05042
- [7] A.J. Hoffman, On the Line Graph of the Complete Bipartite Graph, Ann. Math. Statist. 35 (1964) 883-885, doi: 10.1214/aoms/1177703593. Zbl0127.39302
- [8] S.W. Hruska, On tree congestion of graphs, Discrete Math. 308 (2008) 1801-1809, doi: 10.1016/j.disc.2007.04.030. Zbl1151.05014
- [9] K. Kozawa and Y. Otachi and K. Yamazaki, On spanning tree congestion of graphs, Discrete Math. 309 (2009) 4215-4224, doi: 10.1016/j.disc.2008.12.021. Zbl1232.05116
- [10] C. Löwenstein and D. Rautenbach and F. Regen, On spanning tree congestion, Discrete Math. 309 (2009) 4653-4655, doi: 10.1016/j.disc.2009.01.012. Zbl1213.05093
- [11] R. Laskar and C. Wallis, Chessboard graphs, related designs, and domination parameters, J. Statist. Plann. Inference 76 (1999) 285-294, doi: 10.1016/S0378-3758(98)00132-3. Zbl0939.05065
- [12] H.-F. Law, Spanning tree congestion of the hypercube, Discrete Math. 309 (2009) 6644-6648, doi: 10.1016/j.disc.2009.07.007. Zbl1179.05032
- [13] J.H. Lindsey II, Assignment of numbers to vertices, Amer. Math. Monthly 71 (1964) 508-516, doi: 10.2307/2312587.
- [14] J.W. Moon, On the Line-Graph of the Complete Bigraph, Ann. Math. Statist. 34 (1963) 664-667, doi: 10.1214/aoms/1177704179. Zbl0138.19204
- [15] M.I. Ostrovskii, Minimum congestion spanning trees in planar graphs, Discrete Math. 310 (2010) 1204-1209, doi: 10.1016/j.disc.2009.11.016. Zbl1230.05112
- [16] M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226, doi: 10.1016/j.disc.2004.02.009. Zbl1051.05032
- [17] Y. Otachi, H.L. Bodlaender and E.J. van Leeuwen, Complexity Results for the Spanning Tree Congestion Problem, in: WG 2010, 6410 Lecture Notes in Comput. Sci. (Springer-Verlag, 2010) 3-14. Zbl1308.68067
- [18] S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20 (1987) 235-252, doi: 10.1007/BF01692067. Zbl0643.68094

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.