ART

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 \geq 1 \) is a circulant graph on \( {\displaystyle 3n-1} \) vertices, in which vertex k is connected by an edge to vertices \( {\displaystyle 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 \( {\displaystyle R(3,n)\geq 3(n-1)} \) results, where R(n,k) is the Ramsey number. The equality holds for \( {\displaystyle n=3,n=4} \) only.

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.

Related Items

Petersen graph
Cayley Graph

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License