Andrásfai graph
In graph theory, an Andrásfai graph is a triangle-free circulant graph named after Béla Andrásfai.
Andrásfai graph | |
---|---|
Named after | Béla Andrásfai |
Vertices | |
Edges | |
Diameter | 2 |
Notation | And(n) |
Table of graphs and parameters |
Properties
The Andrásfai graph And(n) 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 And(3).
The graph family is triangle-free, and And(n) has an independence number of . From this the formula results, where is the Ramsey number. The equality holds for only.
gollark: 32-bit java is limited to 4GB heaps.
gollark: It only leads to pain.
gollark: Never run Windows 10 on a server.
gollark: It may not be *using* that for some stupid reason.
gollark: Anyway... you need 64-bit Java, I guess.
References
- Godsil, Chris; Royle, Gordon F. (2013) [2001]. "§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.
- Andrásfai, Béla (1971). Ismerkedés a gráfelmélettel (in Hungarian). Budapest: Tankönyvkiadó. pp. 132–5. OCLC 908973331.
- Weisstein, Eric W. "Andrásfai Graph". MathWorld.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.