## 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).