On the variance of Shannon products of graphs

József Balogh, Clifford Smyth

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)110-118
Number of pages9
JournalDiscrete Applied Mathematics
Volume156
Issue number1
DOIs
StatePublished - 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