On the variance of Shannon products of graphs

József Balogh; Clifford Smyth

doi:10.1016/j.dam.2007.09.008

On the variance of Shannon products of graphs

József Balogh, Clifford Smyth

Mathematics

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1016/j.dam.2007.09.008
State	Published - Jan 1 2008

Keywords

Graph product
Labeling
Variance

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.1016/j.dam.2007.09.008

Library availability

Discover UIUC Full Text

Cite this

@article{b53ac82c2ed248dbb2a59c74cbce8447,

title = "On the variance of Shannon products of graphs",

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.",

keywords = "Graph product, Labeling, Variance",

author = "J{\'o}zsef Balogh and Clifford Smyth",

year = "2008",

month = jan,

day = "1",

doi = "10.1016/j.dam.2007.09.008",

language = "English (US)",

volume = "156",

pages = "110--118",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - On the variance of Shannon products of graphs

AU - Balogh, József

AU - Smyth, Clifford

PY - 2008/1/1

Y1 - 2008/1/1

N2 - 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.

AB - 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.

KW - Graph product

KW - Labeling

KW - Variance

UR - http://www.scopus.com/inward/record.url?scp=35649010951&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35649010951&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2007.09.008

DO - 10.1016/j.dam.2007.09.008

M3 - Article

AN - SCOPUS:35649010951

SN - 0166-218X

VL - 156

SP - 110

EP - 118

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -

On the variance of Shannon products of graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this