Андрашфай график

В теории графов граф Андрашфаи — это циркулянтный граф без треугольников , названный в честь Белы Андрашфаи .

Характеристики

Граф Андрашфаи $And(n)$ для любого натурального числа $n \geq 1$ является циркулянтным графом на $3 n - 1$ вершинах, в котором вершина $k$ соединена ребром с вершинами $k \pm j$ , для каждого $j$ , которое сравнимо с 1 mod 3. Например, граф Вагнера является графом Андрашфаи, графом $And(3)$ .

Семейство графов не содержит треугольников, а $And(n)$ имеет число независимости n . Из этого следует формула $R$ $(3,$ $n$ $) \geq 3($ $n$ $- 1)$ , где $R$ $($ $n$ $,$ $k$ $)$ — число Рамсея . Равенство справедливо только для $n$ $= 3$ $и$ n $=$ $4$ .

Графы Андрашфаи были позднее обобщены. ^[1]^[2]

Ссылки

^ Бисвас, Сучарита; Дас, Ангсуман; Саха, Манидипа (2022). «Обобщенные графы Андрасфаи». Дискуссии Mathematicae – Общая алгебра и приложения . 42 (2): 449–462. дои : 10.7151/dmgaa.1401 . МР 4495565.
^ В. Беденкнехт, GO Mota, Ch. Reiher, M. Schacht, О локальной проблеме плотности для графов заданного нечетного обхвата, Electronic Notes in Discrete Mathematics , том 62, 2017, стр. 39-44.

Библиография

Годсил, Крис; Ройл, Гордон Ф. (2013) [2001]. "§6.10–6.12: Графы Андрашфаи — графы раскраски Андрашфаи, характеристика". Алгебраическая теория графов . Выпускные тексты по математике. Т. 207. Springer. С. 118–123. ISBN 978-1-4613-0163-9.
Андрасфаи, Бела (1977). Введение в теорию графов . Akadémiai Kiadó, Будапешт и Adam Hilger Ltd. Бристоль, Нью-Йорк. п. 268. OCLC 895132932.
Вайсштейн, Эрик В. «График Андрасфаи». Математический мир .

Андрашфай график

Характеристики

Ссылки

Библиография

Связанные элементы