Edge-Bandwidth of Graphs

DOI10.1137/S0895480197330758MaRDI QIDQ4699159zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/math/9904011

zbMATH Keywords

bandwidthcliquestheta graphsbicliquecaterpillarslabelingsedge-bandwidth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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.

Recommendations

• New results on edge-bandwidth
• scientific article; zbMATH DE number 1533071
• On the edge-bandwidth of graph products
• Edge-bandwidth of grids and tori
• Bandwidth and density for block graphs

Cited in

(16)

• A remark on the edge-bandwidth of tori
• 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
• Graph bandwidth of weighted caterpillars
• New bounds on the edge-bandwidth of triangular grids
• scientific article; zbMATH DE number 3963886 (Why is no real title available?)
• Bandwidth of chain graphs
• scientific article; zbMATH DE number 434482 (Why is no real title available?)
• scientific article; zbMATH DE number 1533071 (Why is no real title available?)
• On the edge-bandwidth of graph products
• New results on edge-bandwidth
• scientific article; zbMATH DE number 6453685 (Why is no real title available?)
• Bandwidth of graphs resulting from the edge clique covering problem

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)