Abstract
We study the combinatorial problem of finding an arrangement of distinct integers into the d-dimensional N-cube so that the maximal variance of the numbers on each ℓ-dimensional section is minimized. Our main tool is an inequality on the Laplacian of a Shannon product of graphs, which might be a subject of independent interest. We describe applications of the inequality to multiple description scalar quantizers (MDSQ), to get bounds on the bandwidth of products of graphs, and to balance edge-colorings of regular, d-uniform, d-partite hypergraphs.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 110-118 |
| Number of pages | 9 |
| Journal | Discrete Applied Mathematics |
| Volume | 156 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1 2008 |
Keywords
- Graph product
- Labeling
- Variance
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Fingerprint Dive into the research topics of 'On the variance of Shannon products of graphs'. Together they form a unique fingerprint.
Cite this
Balogh, J., & Smyth, C. (2008). On the variance of Shannon products of graphs. Discrete Applied Mathematics, 156(1), 110-118. https://doi.org/10.1016/j.dam.2007.09.008