On the edge-bandwidth of graph products

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)43-57
Number of pages15
JournalTheoretical Computer Science
Volume359
Issue number1-3
DOIs
StatePublished - Aug 14 2006
Externally publishedYes

Keywords

  • Bandwidth
  • Edge-bandwidth
  • Grid
  • Hypercube
  • Isoperimetric problems
  • Line graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On the edge-bandwidth of graph products'. Together they form a unique fingerprint.

Cite this