Английская Википедия:Andrásfai graph
Шаблон:Short description Шаблон:Infobox 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 Шаблон:Math for any natural number Шаблон:Math is a circulant graph on Шаблон:Math vertices, in which vertex Шаблон:Mvar is connected by an edge to vertices Шаблон:Math, for every Шаблон:Mvar that is congruent to 1 mod 3. For instance, the Wagner graph is an Andrásfai graph, the graph Шаблон:Math.
The graph family is triangle-free, and Шаблон:Math has an independence number of Шаблон:Mvar. From this the formula Шаблон:Math results, where Шаблон:Math is the Ramsey number. The equality holds for Шаблон:Math and Шаблон:Math only.
The Andrásfai graphs were later generalized.[1][2]
References
Bibliography
Related Items
- ↑ A. Das, S. Biswas, M. Saha: Generalized Andrásfai Graphs, Discussiones Mathematicae – General Algebra and Applications 42(2) (2022) 449–462
- ↑ 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.
.jpg){kind=link}