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.W. Bedenknecht, G. O. Mota, Ch. Reiher, M. Schacht, On the local density problem for graphs of given odd-girth, Electronic Notes in Discrete Mathematics, Volume 62, 2017, pp. 39-44.
References
Bibliography
Related Items Petersen graph Cayley graph