The -Andrásfai graph is a circulant graph on nodes whose indices are given by the integers 1, ..., that are congruent to 1 (mod 3). The Andrásfai graphs have graph diameter 2 for , and the -Andrásfai graph has 3-colorings, all of which are equivalent under its automorphism group (Godsil and Royle 2001, p. 119).
The following table summarizes the first few Andrásfai graphs.
The -Andrásfai graph has independence polynomial
with corresponding recurrence equation given by