Andrásfai graph
Named after	Béla Andrásfai
Vertices	${\displaystyle 3n-1}$
Edges	${\displaystyle {\frac {n(3n-1)}{2}}}$
Diameter	2
Chromatic number	${\displaystyle n}$
Properties	Regular graph
Notation	${\displaystyle And(n)}$
Table of graphs and parameters

The "Andrásfai graph" is a triangle free graph on ${\displaystyle 3n-1}$ vertices, named after Béla Andrásfai.

Properties

The Andrásfai-graph for any natural number ${\displaystyle n\geq 1}$ is a circulant graph on ${\displaystyle 3n-1}$ vertices, in which vertex $k$ is connected by an edge to vertices ${\displaystyle k\pm j}$, where ${\displaystyle j=1\mod 3}$.

The graph family is triangle-free, and ${\displaystyle And(n)}$ has an independence number of ${\displaystyle n}$.

References

• Godsil, C., Royle, G .: Algebraic Graph Theory , Springer-Verlag, New York, pp. 118-123, 2001. (§6.10-6.12: The Andrásfai Graphs, Andrásfai Coloring Graphs, A Characterization)
• Andrásfai Béla: Getting to Know the Graphics , Tankönyvkiadó, Budapest, 1971. pp. 132-135.
• Weisstein, Eric W. "Andrásfai Graph". MathWorld.

Related Items

• Petersen graph
• Cayley Graph

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e

Category:Parametric families of graphs Category:Regular graphs