Wykres Andrásfaia

Wykres Andrásfaia
Wykres Andrásfaia
Nazwany po	Béla Andrásfai
Wierzchołki
Krawędzie
Średnica	2
Nieruchomości	Cyrkulacja bez trójkątów ;
Notacja	I ( n )
	Tabela wykresów i parametrów

Dwa rysunki wykresu

And(4).

W teorii grafów graf Andrásfai to pozbawiony trójkątów , okrężny graf nazwany na cześć Béli Andrásfai .

Nieruchomości

Graf Andrásfai $And(n)$ dla dowolnej liczby naturalnej $n \geq 1$ jest grafem kołowym na $3 n - 1$ wierzchołkach, w którym wierzchołek $k$ jest połączony krawędzią z wierzchołkami $k \pm j$ , dla każdego $j$ zgodnego z 1 mod 3 Na przykład graf Wagnera jest grafem Andrásfai, grafem $And(3)$ .

Rodzina grafów nie zawiera trójkątów, a $And() ma$ $n$ liczbę niezależności n . Z tego wynika wzór $R (3, n) \geq 3(n - 1)$ , gdzie $R (n, k)$ jest liczbą Ramseya . Równość obowiązuje tylko dla $n = 3$ i $n = 4$ .

Godsil, Chris; Royle, Gordon F. (2013) [2001]. „§6.10–6.12: Wykresy Andrásfai - wykresy kolorowania Andrásfai, charakterystyka” . Teoria grafów algebraicznych . Absolwent Teksty z matematyki. Tom. 207.Springera. s. 118–123. ISBN 978-1-4613-0163-9 .
Andrásfai, Béla (1971). Ismerkedés a gráfelmélettel (w języku węgierskim). Budapeszt: Tankönyvkiadó. s. 132–5. OCLC 908973331 .
Weisstein, Eric W. „Wykres Andrásfai” . MathWorld .

powiązane przedmioty