Edge-Bandwidth of Graphs
From MaRDI portal
Publication:4699159
DOI10.1137/S0895480197330758zbMATH Open0934.05114arXivmath/9904011OpenAlexW1994701070MaRDI QIDQ4699159FDOQ4699159
Authors: Tao Jiang, Dhruv Mubayi, Aditya Shastri, Douglas B. West 
Publication date: 10 April 2000
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: The edge-bandwidth of a graph is the minimum, over all labelings of the edges with distinct integers, of the maximum difference between labels of two incident edges. We prove that edge-bandwidth is at least as large as bandwidth for every graph, with equality for certain caterpillars. We obtain sharp or nearly-sharp bounds on the change in edge-bandwidth under addition, subdivision, or contraction of edges. We compute edge-bandwidth for cliques, bicliques, caterpillars, and some theta graphs.
Full work available at URL: https://arxiv.org/abs/math/9904011
Recommendations
Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cited In (16)
- The bandwidth problem and operations on graphs
- Bandwidth edge counts for linear arrangements of rectangular grids
- Edge-bandwidth of grids and tori
- Edge-bandwidth of the triangular grid
- Cyclic bandwidth with an edge added
- New bounds on the edge-bandwidth of triangular grids
- Title not available (Why is that?)
- Graph bandwidth of weighted caterpillars
- Bandwidth of chain graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the edge-bandwidth of graph products
- New results on edge-bandwidth
- Title not available (Why is that?)
- Bandwidth of graphs resulting from the edge clique covering problem
- A remark on the edge-bandwidth of tori
This page was built for publication: Edge-Bandwidth of Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4699159)
