THE CYCLIC BANDWIDTH PROBLEM
Yixun Lin · 1994
The cyclic bandwidth problem for a graph G is to label its n venices by the elements of the additive group (Zn, ) of integers modulo n so that the quantity max{d(f(u), f(v)): (u,v) ∈E(G)} is minimized, where f(v) is the label of v∈ V(G) and d(x, y)= min{x (n - y), y (n - x)} represents the distance of x, y ∈ Zn. This paper describes the background of this labelling problem, some basic properties, and the computational complexity. In particular, a local density lower bound for trees and several exact results for special graphs are presented.