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