On the edge-bandwidth of graph products

József Balogh; Dhruv Mubayi; András Pluhár

doi:10.1016/j.tcs.2006.01.046

On the edge-bandwidth of graph products

József Balogh, Dhruv Mubayi, András Pluhár

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

Abstract

The edge-bandwidth of a graph G is the bandwidth of the line graph of G. We show asymptotically tight bounds on the edge-bandwidth of two-dimensional grids and tori, the product of two cliques and the n-dimensional hypercube.

Original language	English (US)
Pages (from-to)	43-57
Number of pages	15
Journal	Theoretical Computer Science
Volume	359
Issue number	1-3
DOIs	https://doi.org/10.1016/j.tcs.2006.01.046
State	Published - Aug 14 2006
Externally published	Yes

Keywords

Bandwidth
Edge-bandwidth
Grid
Hypercube
Isoperimetric problems
Line graph

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1016/j.tcs.2006.01.046

Library availability

Discover UIUC Full Text

Cite this

@article{34c5509e82594fca84af9e4b3c643464,

title = "On the edge-bandwidth of graph products",

abstract = "The edge-bandwidth of a graph G is the bandwidth of the line graph of G. We show asymptotically tight bounds on the edge-bandwidth of two-dimensional grids and tori, the product of two cliques and the n-dimensional hypercube.",

keywords = "Bandwidth, Edge-bandwidth, Grid, Hypercube, Isoperimetric problems, Line graph",

author = "J{\'o}zsef Balogh and Dhruv Mubayi and Andr{\'a}s Pluh{\'a}r",

note = "Funding Information: ∗Corresponding author. E-mail addresses: [email protected] (J. Balogh), [email protected] (D. Mubayi), [email protected] (A. Pluh{\'a}r). 1The first authors research is partially supported by NSF Grant DMS-0302804. 2The second authors research is partially supported by NSF Grant DMS-0400812. 3The third author was partially supported by OTKA Grant T34475.",

year = "2006",

month = aug,

day = "14",

doi = "10.1016/j.tcs.2006.01.046",

language = "English (US)",

volume = "359",

pages = "43--57",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - On the edge-bandwidth of graph products

AU - Balogh, József

AU - Mubayi, Dhruv

AU - Pluhár, András

N1 - Funding Information: ∗Corresponding author. E-mail addresses: [email protected] (J. Balogh), [email protected] (D. Mubayi), [email protected] (A. Pluhár). 1The first authors research is partially supported by NSF Grant DMS-0302804. 2The second authors research is partially supported by NSF Grant DMS-0400812. 3The third author was partially supported by OTKA Grant T34475.

PY - 2006/8/14

Y1 - 2006/8/14

N2 - The edge-bandwidth of a graph G is the bandwidth of the line graph of G. We show asymptotically tight bounds on the edge-bandwidth of two-dimensional grids and tori, the product of two cliques and the n-dimensional hypercube.

AB - The edge-bandwidth of a graph G is the bandwidth of the line graph of G. We show asymptotically tight bounds on the edge-bandwidth of two-dimensional grids and tori, the product of two cliques and the n-dimensional hypercube.

KW - Bandwidth

KW - Edge-bandwidth

KW - Grid

KW - Hypercube

KW - Isoperimetric problems

KW - Line graph

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

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

U2 - 10.1016/j.tcs.2006.01.046

DO - 10.1016/j.tcs.2006.01.046

M3 - Article

AN - SCOPUS:33746349888

SN - 0304-3975

VL - 359

SP - 43

EP - 57

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

On the edge-bandwidth of graph products

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this