User:Porphyro/sandbox

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

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

Properties

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

The graph family is triangle-free, and $And(n)$ has an independence number of $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

Category:Parametric families of graphs Category:Regular graphs