Andrásfai graph
{{short description|Family of triangle-free circulant graphs}}
{{infobox graph
| image = Andrásfai graph And(6).svg
| caption = {{math|And(6)}}
| name = Andrásfai graph
| vertices =
| edges =
| diameter = 2
| namesake = Béla Andrásfai
| chromatic_number =
| properties = Triangle-free
Circulant
| notation = {{math|And(n)}}
}}
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|And(n)}} for any natural number {{math|n ≥ 1}} is a circulant graph on {{math|3n − 1}} vertices, in which vertex {{mvar|k}} is connected by an edge to vertices {{math|k ± j}}, for every {{mvar|j}} that is congruent to 1 mod 3. For instance, the Wagner graph is an Andrásfai graph, the graph {{math|And(3)}}.
The graph family is triangle-free, and {{math|And(n)}} has an independence number of {{mvar|n}}. From this the formula {{math|R(3,n) ≥ 3(n − 1)}} results, where {{math|R(n,k)}} is the Ramsey number. The equality holds for {{math|1=n = 3}} and {{math|1=n = 4}} only.
The Andrásfai graphs were later generalized.{{cite journal|first1=Sucharita |last1=Biswas|first2=Angsuman |last2= Das |first3= Manideepa |last3=Saha|title=Generalized Andrásfai Graphs|journal=Discussiones Mathematicae – General Algebra and Applications|volume=42|number=2|year=2022|pages=449–462|mr=4495565|doi=10.7151/dmgaa.1401|doi-access=free}}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
{{Reflist}}
Bibliography
- {{cite book |first=Chris |last=Godsil |first2=Gordon F. |last2=Royle |title=Algebraic Graph Theory |chapter-url=https://books.google.com/books?id=GeSPBAAAQBAJ&pg=PA118 |date=2013 |orig-year=2001 |publisher=Springer |isbn=978-1-4613-0163-9 |pages=118–123 |chapter=§6.10–6.12: The Andrásfai Graphs—Andrásfai Coloring Graphs, A Characterization |volume=207 |series=Graduate Texts in Mathematics}}
- {{cite book |last=Andrásfai |first=Béla |title=Introductory graph theory|publisher=Akadémiai Kiadó, Budapest and Adam Hilger Ltd. Bristol, New York |location=|year=1977|pages=268|oclc=895132932}}
- {{Mathworld | urlname = AndrasfaiGraph | title = Andrásfai Graph}}