Andrásfai graph
In graph theory, an Andrásfai graph is a triangle-free circulant graph named after.Properties
The Andrásfai graph And for any natural number is a circulant graph on vertices, in which vertex is connected by an edge to vertices for every that is congruent to 1 mod 3. For instance, the Wagner graph is an Andrásfai graph, the graph And.
The graph family is triangle-free, and And has an independence number of. From this the formula results, where is the Ramsey number. The equality holds for only.
