В теории графов , граф Andrásfai является треугольник свободного циркулянта графом именем Белы Andrásfai .
Граф Андрашфаи | |
---|---|
Названный в честь | Бела Андрашфаи |
Вершины | |
Края | |
Диаметр | 2 |
Обозначение | И ( п ) |
Таблица графиков и параметров |
Характеристики
Граф Андрашфаи And ( n ) для любого натурального числа циркулянтный граф на вершины, в которых вершина соединяется ребром с вершинами для каждого это конгруэнтно 1 mod 3. Например, граф Вагнера - это граф Андрашфаи, граф And (3).
Семейство граф-треугольник свободен, и А ( п ) имеет число независимости от. Отсюда формула результаты, где это число Рамсея . Равенство выполняется для Только.
Рекомендации
- Годсил, Крис; Ройл, Гордон Ф. (2013) [2001]. «§6.10–6.12: Графы Андрашфаи - раскраски графов Андрашфаи, характеристика» . Алгебраическая теория графов . Тексты для выпускников по математике. 207 . Springer. С. 118–123. ISBN 978-1-4613-0163-9.
- Андрашфаи, Бела (1971). Ismerkedés a gráfelmélettel (на венгерском языке). Будапешт: Танкёнивкиадо. С. 132–5. OCLC 908973331 .
- Вайсштейн, Эрик В. «График Андрашфаи» . MathWorld .