2014/03/11 by Zevi Miller, Miller, Zevi, Dan Pritikin +4
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #math.CO
paper · pdf · doi:10.48550/arxiv.1403.2749
47 pages, 8 figures
arxiv created 2014/03/11 · openalex publication_date 2014/03/11 · arxiv updated 2014/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G and H be graphs, with |V(H)|≥ |V(G)| , and f:V(G)→ V(H) a one to one map of their vertices. Let dilation(f) = max\ distH(f(x),f(y)): xy∈ E(G) \, where distH(v,w) is the distance between vertices v and w of H. Now let B(G,H) = minf\ dilation(f) \, over all such maps f. The parameter B(G,H) is a generalization of the classic and well studied "bandwidth" of G, defined as B(G,P(n)), where P(n) is the path on n points and n = |V(G)|. Let [a1× a2× ⋯ × ak ] be the k-dimensional grid graph with integer values 1 through ai in the i'th coordinate. In this paper, we study B(G,H) in the case when G = [a1× a2× ⋯ × ak ] and H is the hypercube Qn of dimension n = \lceil log2(|V(G)|) \rceil, the hypercube of smallest dimension having at least as many points as G. Our main result is that B( [a1× a2× ⋯ × ak ],Qn) ≤ 3k, provided ai ≥ 222 for each 1≤ i≤ k. For such G, the bound 3k improves on the previous best upper bound 4k+O(1). Our methods include an application of Knuth's result on two-way rounding and of the existence of spanning regular cyclic caterpillars in the hypercube.