Andrásfai graph
From HandWiki
Short description: Family of triangle-free circulant graphs
| Andrásfai graph | |
|---|---|
.svg) | |
| Named after | Béla Andrásfai |
| Vertices | [math]\displaystyle{ 3n-1 }[/math] |
| Edges | [math]\displaystyle{ \frac{n(3n-1)}{2} }[/math] |
| Diameter | 2 |
| Properties | Triangle-free Circulant |
| Notation | And(n) |
| Table of graphs and parameters | |
.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 And(n) for any natural number n ≥ 1 is a circulant graph on 3n – 1 vertices, in which vertex k is connected by an edge to vertices k ± j, for every j that is congruent to 1 mod 3. For instance, the Wagner graph is an Andrásfai graph, the graph And(3).
The graph family is triangle-free, and And(n) has an independence number of n. From this the formula R(3,n) ≥ 3(n – 1) results, where R(n,k) is the Ramsey number. The equality holds for n = 3 and n = 4 only.
The Andrásfai graphs were later generalized.[1][2]
References
- ↑ 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.
Bibliography
- Godsil, Chris; Royle, Gordon F. (2013). "§6.10–6.12: The Andrásfai Graphs—Andrásfai Coloring Graphs, A Characterization". Algebraic Graph Theory. Graduate Texts in Mathematics. 207. Springer. pp. 118–123. ISBN 978-1-4613-0163-9. https://books.google.com/books?id=GeSPBAAAQBAJ&pg=PA118.
- Andrásfai, Béla (1977). Introductory graph theory. Akadémiai Kiadó, Budapest and Adam Hilger Ltd. Bristol, New York. pp. 268. OCLC 895132932.
- Weisstein, Eric W.. "Andrásfai Graph". http://mathworld.wolfram.com/AndrasfaiGraph.html.
Related Items
 |  |
