Interference patterns in bijective colorings of 2-regular graphs

A bijective coloring of a simple graph of order it is a map from the vertex set of the graph onto {1,2,...,n}. Let f be a bijective coloring of G = (V ,E) with \V\ = n, and let alpha denote an interference parameter in {0,1,2, ...,n - 1}. The interference number of f with respect to G and a is the num ber of edges {u,v} is an element of E for which min{\f(u) - f(v)\, n - \f(u ) - f(v)\} less than or equal to alpha. We address two interference number problems for the family G(2)(n) of all 2-regular graphs of order n. For any given (n,alpha) with 0 less than or equal to alpha less than or equal to n - 1, the first problem is to determine a G is an element of G(2)(n) and a bijective coloring of G whose interference number is as small as possible. Given (n,alpha), the second problem is to determine a G is an element of G( 2)(n) whose minimum interference number over all bijective colorings of G i s as large as possible. Complete solutions are provided for both problems. (C) 2000 Elsevier Science B.V. All rights reserved.