Andrásfai_graph

Andrásfai graph

Andrásfai graph

Family of triangle-free circulant graphs

In graph theory, an Andrásfai graph is a triangle-free, circulant graph named after Béla Andrásfai.

Quick Facts Named after, Vertices ...
Two drawings of the And(4) graph

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.[1][2]

References

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


Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Share this article:

This article uses material from the Wikipedia article Andrásfai_graph, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.