Andrásfai graph explained

Andrásfai graph
Vertices:	3 n -1
Edges:	(n( 3 n -1 ))/(2)
Diameter:	2
Namesake:	Béla Andrásfai
Properties:	Triangle-free Circulant

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.^{[1] [2]}

Bibliography

• Book: Godsil, Chris . Gordon F. . Royle . Algebraic Graph Theory . https://books.google.com/books?id=GeSPBAAAQBAJ&pg=PA118 . 2013 . 2001 . Springer . 978-1-4613-0163-9 . 118–123 . §6.10–6.12: The Andrásfai Graphs—Andrásfai Coloring Graphs, A Characterization . 207 . Graduate Texts in Mathematics.
• Book: Andrásfai, Béla . Introductory graph theory. Akadémiai Kiadó, Budapest and Adam Hilger Ltd. Bristol, New York . 1977. 268. 895132932.

Related Items

• Petersen graph
• Cayley graph

Notes and References

1. Sucharita . Biswas. Angsuman . Das . Manideepa . Saha. Generalized Andrásfai Graphs. Discussiones Mathematicae – General Algebra and Applications. 42. 2. 2022. 449–462. 4495565. 10.7151/dmgaa.1401. free.
2. 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.