Antibandwidth problem for itchy caterpillars

The antibandwidth problem is to label the vertices of a graph of n vertices by 1, 2, 3, ⋯, n bijectively, such that the minimum difference of labels of adjacent vertices is maximized. The antibandwidth problem is known as NP-hard for general graphs. In this paper, we give an antibandwidth labeling scheme for a special class of trees called itchy caterpillar and study the lower bound of antibandwidth problem for the same class of graphs. We also give exact results for some of its subclasses. The result for itchy caterpillars with hair length 1, is the first nontrivial exact result of antibandwidth problem for any class of graphs.