Edge-Bandwidth of Graphs.
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 Kn, Kn,n, caterpillars, and some theta graphs.
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 adjacency matrix has a 1 in those
positions where M is nonzero. Early results on bandwidth are surveyed in [2] and [3].
In this paper, we introduce an analogous parameter for edge-labelings. An edge-
numbering (or edge-labeling) of a graph G is a function f that assigns distinct integers
to the edges of G. We let B 0 (f) denote the maximum of the difference between labels
assigned to adjacent (incident) edges. The edge-bandwidth B 0 (G) is the minimum of B 0 (f)
over all edge-labelings. The term "edge-numbering" is used because we may assume that
f is a bijection from E(G) to the first jE(G)j natural numbers.
We use the notation B 0 (G) for the edge-bandwidth of G because it is immediate that
the edge-bandwidth of a graph equals the bandwidth of its line graph. Thus well-known
y Research supported in part by NSA/MSP Grant MDA904-93-H-3040.
Running head: EDGE-BANDWIDTH
AMS codes: 05C78, 05C35
Keywords: bandwidth, edge-bandwidth, clique, biclique, caterpillar
Written June, 1997.
elementary bounds on bandwidth can be applied to line graphs to obtain bounds on edge-
bandwidth. We mention several such bounds. We compute edge-bandwidth on a special
class where all these bounds are arbitrarily bad.
The relationship between edge-bandwidth and bandwidth is particularly interesting.
Always (G), with equality for caterpillars of diameter more than k in which
every vertex has degree 1 or k + 1. Among forests, B 0 (G) - 2B(G), which is almost sharp
for stars. More generally, if G is a union of t forests, then
Chv'atalov'a and Opatrny [5] studied the effect on bandwidth of edge addition, con-
traction, and subdivision (see [22] for further results on edge addition). We study these
for edge-bandwidth. Adding or contracting an edge at most doubles the edge-bandwidth.
Subdividing an edge decreases the edge-bandwidth by at most a factor of 1=3. All these
bounds are sharp within additive constants. Surprisingly, subdivision can also increase
edge-bandwidth, but at most by 1, and contraction can decrease it by 1.
Because the edge-bandwidth problem is a restriction of the bandwidth problem, it
may be easier computationally. Computation of bandwidth is NP-complete [17], remaining
so for trees with maximum degree 4 [8] and for several classes of caterpillar-like graphs.
Such graphs generally are not line graphs (they contain claws). It remains open whether
computing edge-bandwidth (computing bandwidth of line graphs) is NP-hard.
Due to the computational difficulty, bandwidth has been studied on various special
classes. Bandwidth has been determined for caterpillars and for various generalizations
of caterpillars ([1,11,14,21]), for complete k-ary trees [19], for rectangular and triangular
grids [4,10] (higher dimensions [9,15]), for unions of pairwise internally-disjoint paths with
common endpoints (called "theta graphs" [6,13,18]), etc. Polynomial-time algorithms exist
for computing bandwidth for graphs in these classes and for interval graphs [12,20]. We
begin analogous investigations for edge-bandwidth by computing the edge-bandwidth for
cliques, for equipartite complete bipartite graphs, and for some theta graphs.
2. RELATION TO OTHER PARAMETERS
We begin by listing elementary lower bounds on edge-bandwidth that follow from
standard arguments about bandwidth when applied to line graphs.
PROPOSITION 1. Edge-bandwidth satisfies the following.
a subgraph of G.
are the components of G.
c)
Proof: (a) A labeling of G contains a labeling of H. (b) Concatenating labelings of the
components achieves the lower bound established by (a). (c) The edges incident to a single
vertex induce a clique in the line graph. The lowest and highest among these labels are at
least
PROPOSITION 2.
l
diam (L(H))
Proof: This is the statement of Chung's ``density bound'' [3] for line graphs. Every labeling
of a graph contains a labeling of every subgraph. In a subgraph H, the lowest and
highest labels are at least e(H) \Gamma 1 apart, and the edges receiving these labels are connected
by a path of length at most diam (L(H)), so by the pigeonhole principle some consecutive
pair of edges along the path have labels differing by at least (e(H) \Gamma 1)=diam (L(H)).
Subgraphs of diameter 2 include stars, and a star in a line graph is generated from
an edge of G with its incident edges at both endpoints. The size of such a subgraph is at
most yielding the bound B 0 (G) E(G). This
is at most \Delta(G) \Gamma 1, the lower bound from Proposition 1. Nevertheless, because of the
way in which stars in line graphs arise, they can yield a better lower bound for regular or
nearly-regular graphs. We develop this next.
PROPOSITION 3. For F ' E(G), let @(F ) denote the set of edges not in F
that are incident to at least one edge in F . The edge-bandwidth satisfies
Proof: This is the statement of Harper's ``boundary bound'' [9] for line graphs. Some set
F of k edges must be the set given the k smallest labels. If m edges outside this set have
incidences with this set, then the largest label on the edges of @F is at least k +m, and
the difference between the labels on this and its incident edge in F is at least m.
2.
Proof: We apply Proposition 3 with Each edge uv is incident to d(u)
other edges. Some edge must have the least label, and this establishes the lower bound.
Although these bounds are often useful, they can be arbitrarily bad. The theta graph
is the graph that is the union of m pairwise internally-disjoint paths with
common endpoints and lengths l . The name "theta graph" comes from the case
3. The bandwidth is known for all theta graphs, but settling this was a difficult process
finished in [18]. When the path lengths are equal, the edge-bandwidth and bandwidth both
equal m, using the density lower bound and a simple construction. The edge-bandwidth
can be much higher when the lengths are unequal. Our example showing this will later
demonstrate sharpness of some bounds.
Our original proof of the lower bound was lengthy. The simple argument presented
here originated with Dennis Eichhorn and Kevin O'Bryant. It will be generalized in [7] to
compute edge-bandwidth for a large class of theta graphs.
Example A. Consider
a denote the edges of the ith path of length 3, and let e be the edge incident to all
a i 's at one end and to all c i 's at the other end. Since
2, the first k
edges in the list a are together incident to exactly m other edges,
and larger sets are incident to at most edges. Thus the best lower bound from
Proposition 3 is at most m.
Nevertheless, 3)=2e. For the upper bound, we assign the
labels in order to a's, b's, and c's, inserting e before b dm=2e . The difference between labels
of incidence edges is always at most m except for incidences involving e, which are at most
since e has the middle label.
To prove the lower bound, consider a numbering f
)gg. Comparing the edges
with labels ff; f(e); ff 0 yields I be the interval [ff \Gamma k; ff
By construction, I contains the labels of all a's, all c's, and e. If f(a
then also I. By the choice of ff; ff 0 , avoiding this requires ff
each label is assigned only once and the label f(e) cannot play this
role, only ff \Gamma ff 0 of the b's can have labels outside I. Counting the labels we have forced
into I yields jIj - On the other hand,
Thus k - (3m \Gamma 3)=2, as desired.
3. EDGE-BANDWIDTH VS. BANDWIDTH
In this section we prove various best-possible inequalities involving bandwidth and
edge-bandwidth. The proof that steps. All steps are con-
structive. When f or g is a labeling of the edges or vertices of G, we say that f(e) of g(v)
is the f-label or g-label of the edge e or vertex v. An f-label on an edge incident to u is an
incident f-label of u.
LEMMA 5. If a finite graph G has minimum degree at least two, then
Proof: From an optimal edge-numbering f (such that B 0 we define a
labeling g of the vertices. The labels used by g need not be consecutive, but we show that
when u and v are adjacent.
We produce g in phases. At the beginning of each phase, we choose an arbitrary
unlabeled vertex u and call it the active vertex. At each step in a phase, we select the
unused edge e of smallest f-label among those incident to the active vertex. We let f(e) be
the g-label of the active vertex, mark e used, and designate the other endpoint of e as the
active vertex. If the new active vertex already has a label, we end the phase. Otherwise,
we continue the phase.
When we examine a new active vertex, it has an edge with least incident label, because
every vertex has degree at least 2 and we have not previously reached this vertex. Each
phase eventually ends, because the vertex set is finite and we cannot continue reaching
new vertices. The procedure assigns a label g(u) for each u 2 V (G), since we continue to
a new phase as long as an unlabeled vertex remains.
It remains to verify that E(G). Suppose that
each vertex is assigned the f-label of an incident
edge, we have incident to u; v, respectively. If the edge uv is one of e; e 0 , then e and
e 0 are incident, which implies that jg(u) \Gamma
Otherwise, we have some other value c. We may assume that a ! b by
symmetry. If a ! c and
Thus we may assume that b ? c. In particular, g(v) is not the least f-label incident to v.
The algorithm assigns v a label when v first becomes active, using the least f-label
among unused incident edges. When v first becomes active, only the edge of arrival is a
used incident edge. Thus g(v) is the least incident f-label except when v is first reached via
the least-labeled incident edge. In this case, g(v) is the second smallest incident f-label.
Thus c is the least f-label incident to v and v becomes active by arrival from u. This
requires a and eliminates the bad case.
LEMMA 6. If G is a tree, then
Proof: Again we use an optimal edge-numbering f to define a vertex-labeling g whose
adjacent vertices differ by at most B 0 (f ). We may assume that the least f-label is 1,
occurring on the edge View the edge e
as the root of G. For each vertex
be the f-label of the edge incident
to x along the path from x to the root.
If xy 2 E(G) and xy 6= uv, then we may assume that y is on the path from x to the
root. We have assigned and g(y) is the f-label of an edge incident to y, so
Our labeling g fails to be the desired labeling only because we used 1 on both u and
v. Observe that the largest f-label incident to uv occurs on an edge incident to u or on
an edge incident to v but not both; we may assume the latter. Now we change g(u) to 0.
Because the differences between f(uv) and f-labels on edges incident to u were less than
produces the desired labeling g.
THEOREM 7. For every graph G,
Proof: By Proposition 1b, it suffices to consider connected graphs. Let f be an optimal
edge-numbering of G; we produce a vertex labeling g. Lemma 6 applies when G is a
tree. Otherwise, G contains a cycle, and iteratively deleting vertices of degree 1 produces
a subgraph G 0 in which every vertex has degree at least 2. The algorithm of Lemma
5, applied to the restriction of f to G 0 , produces a vertex labeling g of G 0 in which (1)
adjacent vertices have labels differing by at most B 0 (f ), and (2) the label on each vertex
is the f-label of some edge incident to it in G 0 .
To obtain a vertex labeling of G, reverse the deletion procedure. This iteratively adds
a vertex x adjacent to a vertex y that already has a g-label. Assign to x the f-label of the
edge xy in the full edge-numbering f of G. Now g(x) and g(y) are the f-labels of two edges
incident to y in G, and thus The claims (1) and (2) are preserved,
and we continue this process until we replace all vertices that were deleted from G.
A caterpillar is a tree in which the subtree obtained by deleting all leaves is a path.
One of the characterizations of caterpillars is the existence of a linear ordering of the edges
such that each prefix and each suffix forms a subtree. We show that such an ordering is
optimal for edge-bandwidth and use this to show that Theorem 7 is nearly sharp.
PROPOSITION 8. If G is a caterpillar, then B G be the
caterpillar of diameter d in which every vertex has degree k or 1. If d ? k, then
Proof: Let G be a caterpillar. Let v be the non-leaf vertices of the dominating
path. The diameter of G is d. Number the edges by assigning labels in the following order:
first the pendant edges incident to then the pendant edges incident to v 2 ,
then are incident only at ordering places all pairs
of incident edges within positions of each other. Since B
G, equality holds.
For a caterpillar G with order n and diameter d, Chung's density bound yields B(G) -
G be the caterpillar of diameter d in which every vertex has degree k
1. We have vertices of degree k
d ? k, we have B(G) - k.
On the other hand, we have observed that B 0 (G) - caterpillars. By
Theorem 7, equality holds throughout for these special caterpillars.
Theorem 7 places a lower bound on B 0 (G) in terms of B(G). We next establish an
upper bound. The arboricity is the minimum number of forests needed to partition the
edges of G.
THEOREM 9. If G has arboricity t, then
inequality is almost sharp for stars.
Proof: Given an optimal number g of V (G), we construct a labeling f of E(G). Let
be a decomposition of G into the minimum number of forests. In each component
of each G i , select a root. Each edge of G i is the first edge on the path from one of its
endpoints to the root of its component in G i ; for e 2 E(G i ), let v(e) denote this endpoint.
Each vertex of each forest heads toward the root of its component in that forest along
exactly one edge, so the f-labels of the edges are distinct. Each f-label arises from the g-
label of one of its endpoints. Thus the f-labels of two incident edges arise from the g-labels
of vertices separated by distance at most 2 in G. Also the indices of the forests containing
these edges differ by at most t \Gamma 1. Thus when e; e 0 are incident we have
The star with m edges has bandwidth dm=2e and edge-bandwidth so the
equality is within one of optimality when G is a star.
4. EFFECT OF EDGE OPERATIONS
In this section, we obtain bounds on the effect of local edge operations on the edge-
bandwidth. The variations can be linear in the value of the edge-bandwidth, and our
bounds are optimal except for additive constants. We study addition, subdivision, and
contraction of edges.
THEOREM 10. If H is obtained from G by adding an edge, then
(G). Furthermore, for each k there are examples
Proof: The first inequality holds because G is a subgraph of H. For the second, let g
be an optimal edge-numbering of G; we produce an edge-numbering f of H such that
If e is not incident to an edge of G, form f from g by giving e a new label higher
than the others. If only one endpoint of e is incident to an edge e 0 of G, form f by leaving
the g-labels less than g(e 0 ) unchanged, augmenting the remaining labels by 1, and letting
Thus we may assume that the new edge e joins two vertices of G. Our construction
for this case modifies an argument in [22]. Let e i be the edge such that g(e i
q be the smallest and largest indices of edges of G incident to e,
respectively, and let
The idea in defining f from g is to "fold" the ordering at r, renumbering out from
there so that e p and e q receive consecutive labels, and inserting e just before this. The
renumbering of the old edges is as follows
Finally, let After the edges with g-labels higher than
q or lower than p are exhausted, the new numbering leaves gaps. For edges
we have jf(e the possible added 1 stems from the insertion
of e. When r is between i and j, the actual stretch is smaller.
It remains to consider incidences involving e. Suppose that e is incident to e.
Note that 1 - f(e 0 may assume that 1 - f(e
and e q are incident to the same endpoint of e, then 1 -
If e p and e q are incident to opposite endpoints of e, then e 0 is incident to e p or e q . In these
two cases, we have differs from p or q,
respectively, by at most B(g), we obtain 1
The bound is nearly sharp. Let G be the caterpillar of diameter
of degree used in Proposition 8. Recall that G has vertices and that
k. We form H by adding the edge . The graph H is a cycle of
length k plus pendant edges; each vertex of the cycle has degree k except for two adjacent
vertices of degree k + 1. The diameter of L(H) is bk=2c edges. By
Proposition 2, we obtain B 0 (H)
Subdividing an edge uv means replacing uv by a path u; w; v passing through a new
vertex w. If H is obtained from G by subdividing one edge of G, then H is an elementary
subdivision of G. Edge subdivision can reduce the edge-bandwidth considerably, but it
increases the edge-bandwidth by at most one.
THEOREM 11. If H is an elementary subdivision of G, then (2B 0 (G)+
these bounds are
sharp.
Proof: Suppose that H is obtained from G by subdividing edge e. From an optimal edge-
numbering g of G, we obtain an edge-numbering of H by augmenting the labels greater
than g(e) and letting the labels of the two new edges be g(e) and g(e) + 1. This stretches
the difference between incident labels by at most 1.
To show that this bound is sharp, consider
In Example A, we proved that deleting fb i g from the optimal
numbering there, we obtain a numbering that yields B 1. The graph G 0 is
obtained from G by a sequence of m edge subdivisions, half of which must increase the
edge-bandwidth.
To prove the lower bound on B 0 (H), we consider an optimal edge-numbering f of
H and obtain an edge-numbering of G. For the edges introduced to form H after
deleting e, let may assume that
by leaving the f-labels below p and in [r decreasing those in
[p +1; r] and above q by one, and setting r. The differences between labels on edges
belonging to both G and H change by at most one and increase only when the difference
is less than B 0 (f ). For incidences involving e, the incident edge ffl was incident in H to
e 0 or e 00 . The difference In the
first case, the difference increases by r In the second, it increases by
. Whether B 0 (H)
is even or odd, this establishes the bound claimed.
To show that this bound is sharp, let G be the graph formed by adding
edges at each vertex of K 3 . This graph has 3k edges, and the diameter of its line graph
is 2, so 2. Let x; z be the vertices of the triangle,
with sets X;Y;Z of incident pendant edges, respectively. Let H be the graph obtained
by subdividing xz to obtain x 0 incident to x and z 0 incident to z. Since L(H) has 3k
edges and diameter 3, we have B 0 (H) - k. Assigning 3k labels to E(H) in the order
Replacing x 0 and z 0 with a label for xz in the
middle of Y yields Whether k is even or odd, this achieves the
bound proved above.
Contracting an edge uv means deleting the edge and replacing its endpoints by a single
combined vertex w inheriting all other edge incidences involving u and v. Contraction
tends to make a graph denser and thus increase edge-bandwidth. In some applications,
one restricts attention to simple graphs and thus discards loops or multiple edges that arise
under contraction. Such a convention can discard many edges and thus lead to a decrease
in edge-bandwidth. In particular, contracting an edge of a clique would yield a smaller
clique under this model and thus smaller edge-bandwidth. For the following theorem, we
say that H is an elementary contraction of G if H is obtained from G by contracting
one edge and keeping all other edges, regardless of whether loops or multiple edges arise.
Edge-bandwidth is a valid parameter for multigraphs.
THEOREM 12. If H is an elementary contraction of G, then
these bounds are sharp for each value of B 0 (G).
Proof: Let e be the edge contracted to produce H. For the upper bound, let g be an
optimal edge-numbering of G, and let f be the edge-numbering of H produced by deleting
e from the numbering. In particular, leave the g-labels below g(e) unchanged and decrement
those above g(e) by 1. Edges incident in H have distance at most two in L(G), and
their distance in L(G) is two only if e lies between them. Thus the difference between
their g-labels is at most 2B 0 (g), with equality only if the difference between their f-labels
is
Equality holds when G is the double-star (the caterpillar with two vertices of degree
vertices of degree 1) and e is the central edge of G, so H is the star K 1;2k .
We have observed that B 0
For the lower bound, let f be an optimal edge-numbering of H, and let g be the edge-
numbering of G produced by inserting e into the numbering just above the edge e 0 with
lowest f-label among those incident to the contracted vertex w in H. In particular, leave f-
labels up to f(e 0 ) unchanged, augment those above f(e 0 ) by 1, and let )+1. The
construction and the argument depend on the preservation of loops and multiple edges.
Edges other than e that are incident in G are also incident in H, and the difference between
their labels under g is at most one more than the difference under f . Edges incident to
e in G are incident to e 0 in H and thus have f-label at most f(e
g-label differs from that of e 0 by at most B 0 (f ).
The lower bound must be sharp for each value of B 0 (G), because successive contractions
eventually eliminate all edges and thus reduce the bandwidth.
5. EDGE-BANDWIDTH OF CLIQUES AND BICLIQUES
We have computed edge-bandwidth for caterpillars and other sparse graphs. In this
section we compute edge-bandwidth for classical dense families, the cliques and equipartite
complete bipartite graphs. Give the difficulty of bandwidth computations, the existence
of exact formulas is of as much interest as the formulas themselves.
2.
Proof: Lower bound. Consider an optimal numbering. Among the lowest
values there must be edges involving at least dn=2e vertices of Kn . Among the highest
there must be edges involving at least bn=2c vertices of Kn . Since
incident edges with labels among the lowest
among the highest
1. Therefore,
l nm
nk
l nm
Upper bound. To achieve the bound above, let X;Y be the vertex partition with
ng. We assign the lowest
values to
the edges within X. We use reverse lexicographic order, listing first the edges with higher
vertex 2, then higher vertex 3, etc. We assign the highest
values to the edges within
Y by the symmetric procedure. Thus
Note that the lowest label on an edge incident to vertex dn=2e is 1
The labels between these ranges are assigned to the "cross-edges" between X and Y .
The cross-edges involving the vertex dn=2e 2 X receive the highest of the central labels,
and the cross-edges involving dn=2e not dn=2e) receive the lowest of these
labels. Since the highest cross-edge label is
and the lowest label of an edge
incident to dn=2e is 1+
, the maximum difference between labels on edges incident
to dn=2e is precisely the lower bound on B 0 (Kn ) computed above. This observation holds
symmetrically for the edges incident to dn=2e
We now procede iteratively. On the high end of the remaining gap, we assign the
values to the remaining edges incident to dn=2e \Gamma 1. Then on the low end, we assign values
to the remaining edges incident to dn=2e + 2. We continue alternating between the top
and the bottom, completing the edges incident to the more extreme labels as we approach
the center of the numbering. We have illustrated the resulting order for K 8 . Each time we
insert the remaining edges incident to a vertex of X, the rightmost extreme moves toward
the center at least as much from the previous extreme as the leftmost extreme moves
toward the left. Thus the bound on the difference is maintained for the edges incident to
each vertex. The observation is symmetric for edges incident to vertices of Y .
For equipartite complete bipartite graphs, we have a similar construction involving
low vertices, high vertices, and cross-edges.
\Gamma 1.
Proof: Lower bound. We use the boundary bound of Proposition 3 with
1.
Every set of k edges is together incident to at least n vertices, since a bipartite graph
with n vertices has at most k \Gamma 1 edges. Since K n;n has 2n vertices, at most
edges remain when these vertices are deleted. Thus when jF
We construct an ordering achieving this bound. Let
fy be the partite sets. Order the vertices as We alternately
finish a vertex from the beginning of L and a vertex from the end. When finishing
a vertex from the beginning, we place its incident edges to vertices earlier in L at the
end of the initial portion of the numbering f that has already been determined. When
finishing a vertex from the end of L, we place its incident edges to vertices later in L at
the beginning of the terminal portion of f that has been determined. We do not place an
edge twice. When we have finished each vertex in each direction, we have placed all edges
in the numbering. For example, this produces the following edge ordering for
It suffices to show that for the jth vertex v j 2 L, there are at least n
edges that come before the first edge incident to v or after the last edge incident to v. For
are exactly
edges before the first appearance of v j and exactly
edges after its last appearance, which matches the argument in the lower
bound. As j decreases, the leftmost appearance of v j moves leftward no more quickly than
the rightmost appearance; we omit the numerical details. The symmetric argument applies



--R


The bandwidth problem for graphs and matrices - a survey
Labelings of graphs
Optimal labelling of a product of two paths
The bandwidth problem and operations on graphs
The bandwidth of theta graphs
The edge-bandwidth of theta graphs (in preparation)
Complexity results for bandwidth minimization.
Optimal assignments of numbers to vertices
On the bandwidth of triangulated triangles

Computing the bandwidth of interval graphs
The bandwidth of the graph formed by n meridian lines on a sphere (Chi- nese
The bandwidth of caterpillar graphs
Compression operators and a solution to the bandwidth problem of the product of n paths
The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete

Bandwidth of theta graphs with short paths.
Bandwidth of the complete k-ary tree
An O(n log n) algorithm for bandwidth of interval graphs

Maximum bandwidth under edge addition
--TR

--CTR
Balogh , Dhruv Mubayi , Andrs Pluhr, On the edge-bandwidth of graph products, Theoretical Computer Science, v.359 n.1, p.43-57, 14 August 2006
Tiziana Calamoneri , Annalisa Massini , Imrich Vro, New results on edge-bandwidth, Theoretical Computer Science, v.307 n.3, p.503-513, 14 October
Oleg Pikhurko , Jerzy Wojciechowski, Edge-bandwidth of grids and tori, Theoretical Computer Science, v.369 n.1, p.35-43, 15 December 2006
bandwidth;edge-bandwidth;biclique;caterpillar;clique