Andrásfai graph
In graph theory, an Andrásfai graph is a triangle-free, circulant graph named after Béla Andrásfai.
Properties
The Andrásfai graph 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.The graph family is triangle-free, and has an independence number of. From this the formula results, where is the Ramsey number. The equality holds for and only.
The Andrásfai graphs were later generalized.