Andrásfai graph

The Andrásfai graph And(n) for any natural number ${\displaystyle n\geq 1}$ is a circulant graph on ${\displaystyle 3n-1}$ vertices, in which vertex ${\displaystyle k}$ is connected by an edge to vertices ${\displaystyle k\pm j,}$ for every ${\displaystyle j}$ that is congruent to 1 mod 3. For instance, the Wagner graph is an Andrásfai graph, the graph And(3).

The graph family is triangle-free, and And(n) has an independence number of ${\displaystyle n}$. From this the formula ${\displaystyle R(3,n)\geq 3(n-1)}$ results, where ${\displaystyle R(n,k)}$ is the Ramsey number. The equality holds for ${\displaystyle n=3,n=4}$ only.

• Godsil, Chris; Royle, Gordon F. (2013) [2001]. "§6.10–6.12: The Andrásfai Graphs—Andrásfai Coloring Graphs, A Characterization". Algebraic Graph Theory. Graduate Texts in Mathematics. Vol. 207. Springer. pp. 118–123. ISBN 978-1-4613-0163-9.
• Andrásfai, Béla (1971). Ismerkedés a gráfelmélettel (in Hungarian). Budapest: Tankönyvkiadó. pp. 132–5. OCLC 908973331.
• Weisstein, Eric W. "Andrásfai Graph". MathWorld.

• Petersen graph
• Cayley graph