mathworld.wolfram.com

Andrásfai Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
  • ️Thu Jan 31 2008
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

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.

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