PDF

Discussiones Mathematicae Graph Theory 31(4) (2011) 753-761
DOI: https://doi.org/10.7151/dmgt.1577

Spanning Tree Congestion of Rook's Graphs

Kyohei Kozawa Electric Power Development Co., Ltd. 6--15--1, Ginza, Chuo-ku, Tokyo, 104--8165, Japan

Yota Otachi Graduate School of Information Sciences Tohoku University Sendai 980--8579, Japan

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_m ☐ K_n for any m and n.

Keywords: spanning tree congestion, Rook's graph

2010 Mathematics Subject Classification: 05C05 (05C76).

References

[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.
[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.
[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).
[4]	H.L. Bodlaender, K. Kozawa, T. Matsushima and Y. Otachi, Spanning Tree Congestion of k-outerplanar Graphs, in: WAAC 2010 (2010) 34--39.
[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.
[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.
[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.
[8]	S.W. Hruska, On tree congestion of graphs, Discrete Math. 308 (2008) 1801--1809, doi: 10.1016/j.disc.2007.04.030 .
[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.
[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.
[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.
[12]	H.-F. Law, Spanning tree congestion of the hypercube, Discrete Math. 309 (2009) 6644--6648, doi: 10.1016/j.disc.2009.07.007.
[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 .
[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.
[16]	M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219--226, doi: 10.1016/j.disc.2004.02.009.
[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.
[18]	S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20 (1987) 235--252, doi: 10.1007/BF01692067.

Received 3 August 2010
Revised 15 November 2010
Accepted 15 November 2010