TOPICS
Search

Andrásfai Graph


AndrasfaiGraphs

The n-Andrásfai graph is a circulant graph on 3n-1 nodes whose indices are given by the integers 1, ..., 3n-1 that are congruent to 1 (mod 3). The Andrásfai graphs have graph diameter 2 for n>1, and the n-Andrásfai graph has 6(3n-1) 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.

nnamecirculant notation
12-path graphCi_2(1)
25-cycle graphCi_5(1)
34-Möbius ladderCi_8(1,4)
44-Andrásfai graphCi_(11)(1,4)
55-Andrásfai graphCi_(14)(1,4,7)
66-Andrásfai graphCi_(17)(1,4,7)

The n-Andrásfai graph has independence polynomial

 I_n(x)=1+(3n-1)x(x+1)^(n-1),

with corresponding recurrence equation given by

 I_n(x)=(2x+3)I_(n-1)(x)-(x+1)(x+3)I_(n-2)(x)+(x+1)^2I_(n-3)(x),

See also

Circulant Graph

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Andrásfai Graph

Cite this as:

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

Subject classifications