Circulants and Sequences
Karen L. Collins · SIAM Journal on Discrete Mathematics · 1998
A graph G is stable if its normalized chromatic difference sequence is equal to the normalized chromatic difference sequence of G X G, the Cartesian product of G with itself. Let $\alpha$ be the independence number of G and let $\omega$ be its clique number. Suppose that G has n vertices. We show that the first $\omega$ terms of the normalized chromatic difference 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 normalized chromatic difference sequence are $\alpha/n,\alpha/n,\beta/n$, where $\beta \geq \alpha/k$. We derive from this sequence an upper bound on the independence ratio of G, which agrees with the lower bound of Häggkvist for $k=2$ and of Albertson, Chan, and Haas for $k\geq 3$ [Ann. Discrete Math., 13 (1982), pp. 89--100; linebreak[4]J. Graph Theory, 17 (1993), pp. 581--588]. Zhou has shown that circulants and finite abelian Cayley graphs are stable. Let G be a circulant 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=\{a_1,a_2,\ldots,a_s\}$ is reversible if $a_1+a_s= a_2+a_{s-1}=\cdots=a_{\lfloor \frac{s}{2}\rfloor}+a_{\lceil \frac{s}{2}\rfloor}$. We show that the independence ratio $\mu(G)\leq \mu(S)$ and that if S is reversible, then $\lim_{n\rightarrow\infty}\mu(G)=\mu(S)$. We conjecture that $\mu(G)=\mu(S)$ for a reversible circulant with sufficiently many vertices.