Misplaced Pages

Andrásfai graph
Named after	Béla Andrásfai
Vertices	${\displaystyle 3n-1}$
Edges	${\displaystyle {\frac {n(3n-1)}{2}}}$
Diameter	2
Properties	Triangle-free Circulant
Notation	And(n)
Table of graphs and parameters

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.

References

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

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. Vol. 207. Springer. pp. 118–123. ISBN 978-1-4613-0163-9.
• Andrásfai, Béla (1977). Introductory graph theory. Akadémiai Kiadó, Budapest and Adam Hilger Ltd. Bristol, New York. p. 268. OCLC 895132932.
• Weisstein, Eric W. "Andrásfai Graph". MathWorld.

Related Items

• Petersen graph
• Cayley graph

This graph theory-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Parametric families of graphs
• Regular graphs
• Graph theory stubs