×

The bisection width and the isoperimetric number of arrays. (English) Zbl 1050.05069

A \(d\)-dimensional array \(A^d\) is a graph with \(k_1\times \cdots\times k_d\) vertices, \(k_i<k_{i+1}\), each having a unique label \(l=(l_1,\dots,l_d)\), where \(0<l_i <k_{i-1}\). There is an edge between two vertices if their labels differ in exactly one dimension and the difference is exactly one. The authors prove that the bisection width bw\((A^d)\) is given by \( \text{bw}(A^d)= \sum^d_{i=e}K_i\), where \(e\) is the largest index for which \(k_e\) is even (if it exists, \(e=1\) otherwise) and \(K_i=k_{i-1}\) of \(k_{i-2}\cdots k_1\). They also show that the edge-isoperimetric number \(i(A^d)\) is given by \(i(A^d)=1/[k_d/2]\), where \([a]\) is the integral part \(a\).

MSC:

05C35 Extremal problems in graph theory
Full Text: DOI

References:

[1] M.C. Azizoğlu, Ö. Eğecioğlu, The isoperimetric number and the bisection width of generalized cylinders, Electronic Notes in Discrete Mathematics, Vol. 11, July 2002.; M.C. Azizoğlu, Ö. Eğecioğlu, The isoperimetric number and the bisection width of generalized cylinders, Electronic Notes in Discrete Mathematics, Vol. 11, July 2002. · Zbl 1050.05069
[2] M.C. Azizoğlu, Ö. Eğecioğlu, The edge-isoperimetric number of generalized cylinders, Technical Report TRCS99-13, Department of Computer Science, University of California, Santa Barbara, April 1999.; M.C. Azizoğlu, Ö. Eğecioğlu, The edge-isoperimetric number of generalized cylinders, Technical Report TRCS99-13, Department of Computer Science, University of California, Santa Barbara, April 1999. · Zbl 1320.05063
[3] M.C. Azizoğlu, Ö. Eğecioğlu, Extremal sets minimizing dimension-normalized boundary in Hamming graphs, SIAM J. Discrete Math, in press.; M.C. Azizoğlu, Ö. Eğecioğlu, Extremal sets minimizing dimension-normalized boundary in Hamming graphs, SIAM J. Discrete Math, in press. · Zbl 1041.05041
[4] S.L. Bezrukov, Edge isoperimetric problems on graphs, in: L. Lovasz, A. Gyarfas, G.O.H. Katona, A. Recski, L. Szekely (Eds.), Graph Theory and Combinatorial Biology, Bolyai Society Mathematical Studies, Vol. 7, Budapest, 1999, pp. 157-197.; S.L. Bezrukov, Edge isoperimetric problems on graphs, in: L. Lovasz, A. Gyarfas, G.O.H. Katona, A. Recski, L. Szekely (Eds.), Graph Theory and Combinatorial Biology, Bolyai Society Mathematical Studies, Vol. 7, Budapest, 1999, pp. 157-197. · Zbl 0927.05080
[5] F.R.K. Chung, Spectral Graph Theory, AMS Regional Conference Series in Mathematics, Vol. 92, 1997.; F.R.K. Chung, Spectral Graph Theory, AMS Regional Conference Series in Mathematics, Vol. 92, 1997. · Zbl 0867.05046
[6] Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays · Trees · Hypercubes (1992), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo, CA · Zbl 0743.68007
[7] Mohar, B., Isoperimetric numbers of graphs, J. Combin. Theory, Ser. B, 47, 274-291 (1989) · Zbl 0719.05042
[8] Nakano, K., Linear layouts of generalized hypercubes, (van Leeuwen, Jan, Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 790 (1993), Springer: Springer Berlin), 364-375 · Zbl 1528.68315
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.