Name
Title | ||
|---|---|---|
Asymptotic Determination of Edge-Bandwidth of Multidimensional Grids and Hamming Graphs |
Abstract | ||
|---|---|---|
The edge-bandwidth $B'(G)$ of a graph $G$ is the bandwidth of the line graph of $G$. More specifically, for any bijection $f: E(G)\to \{1,2,\ldots, |E(G)|\}$, let $B'(f,G)=\max\{|f(e_1)- f(e_2)|: \mbox{$e1$ and $e2$ are incident edges of $G$}\}$, and let $B'(G)=\min_f B'(f,G)$. We determine asymptotically the edge-bandwidth of $d$-dimensional grids $P_n^d$ and of the Hamming graph $K_n^d$, the $d$-fold Cartesian product of $K_n$. Our results are as follows. (i) For fixed $d$ and $n\to \infty$, $B'(P_n^d)=c(d)d n^{d-1}+O(n^{d-{3\over2}})$, where $c(d)$ is a constant depending on $d$, which we determine explicitly. (ii) For fixed even $n$ and $d\to \infty$, $B'(K_n^d)=(1+o(1))\sqrt{d\over {2\pi}}\, n^d (n-1)$. Our results extend recent results by Balogh, Mubayi, and Pluhár [Theoret. Comput. Sci., 359 (2006), pp. 43-57], who determined $B'(P_n^2)$ asymptotically as a function of $n$ and $B'(K_2^d)$ asymptotically as a function of $d$. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/060660291 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
cartesian product,line graph,hamming graphs,multidimensional grids,hamming graph,boundary,bandwidth,isoperimetric problem,grid,edge-bandwidth,asymptotic determination,incident edge,recent result,dimensional grid,min_f b | Graph,Discrete mathematics,Combinatorics,Line graph,Bijection,Cartesian product,Isoperimetric inequality,Mathematics,Hamming graph | Journal |
Volume | Issue | ISSN |
22 | 2 | 0895-4801 |
Citations | PageRank | References |
2 | 0.42 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Reza Akhtar | 1 | 23 | 4.05 |
| Tao Jiang | 2 | 38 | 4.62 |
| Zevi Miller | 3 | 161 | 31.65 |