Extremal Sets Minimizing Dimension-Normalized Boundary in Hamming Graphs

2003/01/01 by M. Cemil Azizouglu, Ömer Eugeciouglu · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #VLSI and FPGA Design Techniques #Mathematics #Combinatorics #Lexicographical order #Vertex (graph theory) #Isoperimetric inequality #Discrete mathematics #Hamming graph #Graph #Dimension (graph theory) #Hamming code #Algorithm #Decoding methods #Block code

paper · doi:10.1137/s0895480100375053

openalex publication_date 2003/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

We prove that the set of first k vertices of a Hamming graph in reverse-lexicographic order constitutes an extremal set minimizing the dimension-normalized edge-boundary over all k-vertex subsets of the graph. This generalizes a result of Lindsey and can be used to prove a tight lower bound for the isoperimetric number and the bisection width of arrays.

Citations

• Spectral graph theory [CBMS Conference on Recent Advances in Spectral Graph Theory held at California State University at Fresno, June 6 - 10. 1994]

Cited by

• Rook's graph [wikipedia]