Andrásfai graph
Template:Short description Template:Infobox graph
.jpg)
In graph theory, an Andrásfai graph is a triangle-free, circulant graph named after Béla Andrásfai.
Properties
The Andrásfai graph Template:Math for any natural number Template:Math is a circulant graph on Template:Math vertices, in which vertex Template:Mvar is connected by an edge to vertices Template:Math, for every Template:Mvar that is congruent to 1 mod 3. For instance, the Wagner graph is an Andrásfai graph, the graph Template:Math.
The graph family is triangle-free, and Template:Math has an independence number of Template:Mvar. From this the formula Template:Math results, where Template:Math is the Ramsey number. The equality holds for Template:Math and Template:Math only.
The Andrásfai graphs were later generalized.[1][2]
References
Bibliography
Related Items
- ↑ Template:Cite journal
- ↑ 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.