El grafo de Andrásfai And( n ) para cualquier número natural n ≥ 1 es un grafo circulante en 3 n – 1 vértices, en el que el vértice k está conectado por una arista a los vértices k ± j , para cada j que sea congruente con 1 mod 3. Por ejemplo, el grafo de Wagner es un grafo de Andrásfai, el grafo And(3) .
La familia de grafos no tiene triángulos y And( n ) tiene un número de independencia de n . De esto resulta la fórmula R (3, n ) ≥ 3( n – 1) , donde R ( n , k ) es el número de Ramsey . La igualdad se cumple solo para n = 3 y n = 4 .
Los gráficos de Andrásfai se generalizaron posteriormente. [1] [2]
Referencias
^ Biswas, Sucharita; Das, Angsuman; Saha, Manideepa (2022). "Gráficos de Andrásfai generalizados". Discussiones Mathematicae - Álgebra general y aplicaciones . 42 (2): 449–462. doi : 10.7151/dmgaa.1401 . SEÑOR 4495565.
^ W. Bedenknecht, GO Mota, Ch. Reiher, M. Schacht, Sobre el problema de densidad local para gráficos de circunferencia impar dada, Notas electrónicas en matemáticas discretas , Volumen 62, 2017, págs. 39-44.
Bibliografía
Godsil, Chris; Royle, Gordon F. (2013) [2001]. "§6.10–6.12: Los grafos de Andrásfai: grafos de coloración de Andrásfai, una caracterización". Teoría de grafos algebraicos . Textos de posgrado en matemáticas. Vol. 207. Springer. págs. 118–123. ISBN 978-1-4613-0163-9.
Andrásfai, Béla (1977). Introducción a la teoría de grafos . Akadémiai Kiadó, Budapest y Adam Hilger Ltd. Bristol, Nueva York. pag. 268. OCLC 895132932.
.jpg/1280px-Andr%C3%A1sfai-gr%C3%A1f_(n=4).jpg)