CIRCULANTS AND SEQUENCES

A graph G is stable if its normalized chromatic difference sequence is equal to the normalized chromatic difference sequence of G x G, the C artesian product of G with itself. Let alpha be the independence numbe r of G and let omega be its clique number. Suppose that G has n vertic es. We show that the first omega terms of the normalized chromatic dif ference sequence of a stable graph G must be alpha/n and further show that if G has odd girth 2k + 1, then the first three terms of its norm alized chromatic difference sequence are alpha/n, alpha/n, beta/n, whe re beta greater than or equal to alpha/k. We derive from this sequence an upper bound on the independence ratio of G, which agrees with the lower bound of Haggkvist for k = 2 and of Albertson, Chan, and Haas fo r k greater than or equal to 3 [Ann. Discrete Math., 13 (1982), pp. 89 -100; J. Graph Theory, 17 (1993), pp. 581-588]. Zhou has shown that ci rculants and finite abelian Cayley graphs are stable. Let G be a circu lant with symbol set S and n vertices [Discrete Math., 90 (1991), pp. 297-311; Discrete Appl. Math., 41 (1993), pp. 263-267]. We say that S = {alpha(1),alpha(2),...alpha(s)} is reversible if alpha(1) + alpha(s) = alpha(2) + alpha(s-1) = ... = alpha([s/2]) + alpha([s/2]). We show that the independence ratio mu(G) less than or equal to mu(S) and that if S is reversible, then lim(n-->infinity) mu(G) = mu(S). We conjectu re that mu(G) = mu(S) for a reversible circulant with sufficiently man y vertices.