CYCLIC ANTIBANDWIDTH OF GRAPHS: CHARACTERIZATION AND PARAMETER BOUNDS

Abstract

Let  be a graph on  vertices. The cyclic antibandwidth of  is a circular labeling parameter that measures the minimum cyclic distance between the labels of adjacent vertices. A known characterization of cyclic antibandwidth of graph states that  if and only if the th power of the cycle  is contained in the complement of . This characterization provides a natural extremal comparison graph and allows us to derive bounds on the cyclic antibandwidth in terms of several classical graph parameters, including the number of edges, maximum degree, independence number, vertex cover number, vertex connectivity, and chromatic number. We also obtain further consequences for special classes of graphs, particularly bipartite graphs and trees.