TOPICS

# Andrásfai Graph

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

Circulant Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Andrásfai, B. "Graphentheoretische Extremalprobleme." Acta Math. Acad. Sci. Hungar. 15, 413-438, 1964.Andrásfai, B. Introductory Graph Theory. Elmsford, NY: Pergamon Press, 1977.Brouwer, A. E. "Finite Graphs in Which the Point Neighbourhoods Are the Maximal Independent Sets." In From Universal Morphisms to Megabytes: A Baayen Space Odyssey. Amsterdam, Netherlands: Math. Centrum Wisk. Inform., pp. 231-233, 1994.Godsil, C. and Royle, G. "The Andrásfai Graphs," "Colouring Andrásfai Graphs," and "A Characterization." §6.10-6.12 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 118-123, 2001.Pach, J. "Graphs Whose Every Independent Set Has a Common Neighbour." Disc. Math. 31, 217-228, 1981.

Andrásfai Graph

## Cite this as:

Weisstein, Eric W. "Andrásfai Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AndrasfaiGraph.html