2011/01/05 by Yota Otachi, Otachi, Yota, Ryohei Suda +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph theory and applications #Interconnection Networks and Systems #cs.DM
paper · pdf · doi:10.48550/arxiv.1101.0964
11 pages
arxiv created 2011/01/05 · openalex publication_date 2011/01/05 · arxiv updated 2011/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors.