Andrásfai graph

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

Andrásfai graph
Named afterBéla Andrásfai
Vertices
Edges
Diameter2
NotationAnd(n)
Table of graphs and parameters
Two drawings of the And(4) graph

Properties

The Andrásfai graph And(n) for any natural number is a circulant graph on vertices, in which vertex is connected by an edge to vertices for every 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 . From this the formula results, where is the Ramsey number. The equality holds for 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.


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