Andrásfai graph

Andrásfai graph
Andrásfai graph
Named after	Béla Andrásfai
Vertices
Edges
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.

Two drawings of the

And(4)

graph

Properties

The Andrásfai graph $And(n)$ for any natural number $n \geq 1$ is a circulant graph on $3 n - 1$ vertices, in which vertex $k$ is connected by an edge to vertices $k \pm 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) \geq 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) [2001]. "§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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] A. Das, S. Biswas, M. Saha: Generalized Andrásfai Graphs, Discussiones Mathematicae – General Algebra and Applications 42(2) (2022) 449–462

[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.