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.
name | circulant notation | |
1 | 2-path graph | |
2 | 5-cycle graph | |
3 | 4-Möbius ladder | |
4 | 4-Andrásfai graph | |
5 | 5-Andrásfai graph | |
6 | 6-Andrásfai graph |
The -Andrásfai graph has independence polynomial
with corresponding recurrence equation given by