Automatically assigned DDC number: 5115

Manually assigned DDC number: 5115

Number of references: 0

Title: Edge-Bandwidth Of Graphs

Author:

Author:

Author:

Subject: Tao Jiang,Dhruv Mubayi,Aditya Shastri Edge-Bandwidth Of Graphs

Description: . 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 nearlysharp bounds on the change in edge-bandwidth under addition, subdivision, or contraction of edges. We compute edge-bandwidth for Kn , K n;n , caterpillars, and some theta graphs. 1. INTRODUCTION A classical optimization problem is to label the vertices of a graph with distinct integers so that the maximum difference between labels on adjacent vertices is minimized. For a graph G, the optimal bound on the differences is the bandwidth B(G). The name arises from computations with sparse symmetric matrices, where operations run faster when the matrix is permuted so that all entries lie near the diagonal. The bandwidth of a matrix M is the bandwidth of the corresponding graph whose...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-11-10

Pubyear: 0

Format: ps

Identifier: http://citeseer.ist.psu.edu/140524.html

Source: http://www.math.uiuc.edu/~west/edgeband.ps

Language: en

Rights: unrestricted