DMGT

Discussiones Mathematicae Graph Theory 29(3) (2009) 511-519
DOI: https://doi.org/10.7151/dmgt.1461

MINIMUM CONGESTION SPANNING TREES OF GRIDS AND DISCRETE TORUSES

Alberto Castejón

Department of Applied Mathematics I
Higher Technical School of Telecommunications Engineering (ETSIT)
Universidad de Vigo Lagoas-Marcosende
36200 Vigo (Pontevedra), Spain
e-mail: acaste@uvigo.es

Mikhail I. Ostrovskii

Department of Mathematics and Computer Science
St. John's University
8000 Utopia Parkway, Queens, NY 11439, USA
e-mail: ostrovsm@stjohns.edu

Abstract

The paper is devoted to estimates of the spanning tree congestion for grid graphs and discrete toruses of dimensions two and three.

Keywords: minimum congestion spanning tree, grid graph, discrete torus.

2000 Mathematics Subject Classification: Primary: 05C05;
Secondary: 05C35.

References

[1]	R. Ahlswede and S.L. Bezrukov, Edge isoperimetric theorems for integer point arrays, Appl. Math. Lett. 8 (1995) 75-80, doi: 10.1016/0893-9659(95)00015-I.
[2]	B. Bollobás and I. Leader, Edge-isoperimetric inequalities in the grid, Combinatorica 11 (1991) 299-314, doi: 10.1007/BF01275667.
[3]	J. Clark and D.A. Holton, A First Look at Graph Theory (World Scientific, River Edge, N.J., 1991).
[4]	R. Cypher, Theoretical aspects of VLSI pin limitations, SIAM J. Comput. 22 (1993) 356-378, doi: 10.1137/0222027.
[5]	F. Harary, Graph Theory (Addison-Wesley Publishing Company, 1969).
[6]	C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869) 185-190, doi: 10.1515/crll.1869.70.185.
[7]	M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226, doi: 10.1016/j.disc.2004.02.009.
[8]	M.I. Ostrovskii, Sobolev spaces on graphs, Quaestiones Mathematicae 28 (2005) 501-523, doi: 10.2989/16073600509486144.
[9]	M.I. Ostrovskii, Minimum congestion spanning trees in bipartite and random graphs, preprint, 2007.
[10]	M. Snir, I/O limitations on multi-chip VLSI systems, in: 19th Allerton Conference on Communication, Control, and Computing, 1981, pp. 224-231.
[11]	B.Y. Wu and K.-M. Chao, Spanning trees and optimization problems (Boca Raton, Chapman & Hall/CRC, 2004).

Received 28 February 2008
Accepted 30 September 2008