Граф Фолкмана

Перейти к навигации Перейти к поиску

Граф Фолкмана
Граф Фолкмана
Назван в честь	Дж. Фолкмана
Вершин	20
Рёбер	40
Радиус	3
Диаметр	4
Обхват	4
Автоморфизмы	3840
Хроматическое число	2
Хроматический индекс	4
Свойства	Двудольный Гамильтонов Полусимметричный Регулярный Эйлеров Совершенный
Медиафайлы на Викискладе

Граф Фолкмана (названный именем Джона Фолкмана) — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами^[1].

Граф Фолкмана является гамильтоновым и имеет хроматическое число 2, хроматический индекс 4, радиус 3, диаметр 4 и обхват 4. Он также является вершинно 4-связным, рёберно 4-связным и совершенным. Граф имеет книжное вложение 3 и число очередей 2^[2].

Алгебраические свойства

Группа автоморфизмов графа Фолкмана действует транзитивно на его рёбра, но не на его вершины. Это наименьший неориентированный граф, который является рёберно-транзитивным и регулярным, но не вершинно транзитивным^[3]. Такие графы называются полусимметричными, их первым изучал Фолкман в 1967 и обнаружил граф с 20 вершинами, который был позже назван его именем^[4].

Как полусимметричный граф, граф Фолкмана является двудольным и его группа автоморфизмов действует транзитивно на каждую долю вершин двудольного графа. На диаграмме ниже, показывающей хроматическое число графа, зелёные вершины не могут быть отражены в красные каким-либо автоморфизмом, но любая красная вершина может быть отражена в любую другую красную вершину, а любая зелёная — в любую другую зелёную вершину.

Характеристический многочлен графа Фолкмана равен $(x-4)x^{10}(x+4)(x^{2}-6)^{4}$ .

Галерея

Хроматический индекс графа Фолкмана равен 4.
Хроматическое число графа Фолкмана равно 2.
Граф Фолкмана является гамильтоновым.

Примечания

↑ Weisstein, Eric W. Folkman graph (англ.) на сайте Wolfram MathWorld.
↑ Wolz, 2018.
↑ Skiena, 1990, с. 186-187.
↑ Folkman, 1967, с. 215–232.

Литература

Skiena S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading. — MA: Addison-Wesley, 1990.
Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).
Folkman J. Regular line-symmetric graphs // Journal of Combinatorial Theory. — 1967. — Т. 3, вып. 3. — doi:10.1016/S0021-9800(67)80069-3.

Похожие исследовательские статьи

Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.

В теории графов вершинно-транзитивным графом называется граф G такой, что для любых двух вершин v₁ и v₂ графа G существует автоморфизм

\text{[math]}

В теории графов рёберно-транзитивным называется такой граф G, для двух любых рёбер которого e₁ и e₂ существует автоморфизм, отображающий e₁ в e₂.

Граф Фрухта — определённый планарный минимальный кубический граф, не имеющий нетривиальных автоморфизмов. Описан Робертом Фрухтом в 1939 году.

Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u₁—v₁ и u₂—v₂ имеется автоморфизм:

f : V(G) → V(G)

Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.

Граф Дика — 3-регулярный граф с 32 вершинами и 48 рёбрами, назван в честь Вальтера фон Дика .

Граф Фостера — двудольный 3-регулярный граф с 90 вершинами и 135 рёбрами. Граф Фостера является гамильтоновым, имеет хроматическое число 2, хроматический индекс 3, радиус 8, диаметр 8 и обхват 10. Также является вершинно 3-связным и рёберно 3-связным.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

Граф Вагнера — 3-регулярный граф с 8 вершинами и 12 рёбрами, является 8-вершинной лестницей Мёбиуса.

В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

Граф F26A — симметричный двудольный кубический граф с 26 вершинами и 39 рёбрами.

Граф Любляны — неориентированный двудольный граф с 112 вершинами и 168 рёбрами.

Полусимметричный граф — неориентированный рёберно-транзитивный регулярный граф, не являющийся вершинно-транзитивным. Другими словами, граф полусимметричен, если каждая вершина имеет одно и то же число инцидентных рёбер и для каждой пары рёбер существует симметрия, переводящая одно ребро в другое, однако есть некоторая пара вершин, для которой нет симметрии, переводящей одну вершину в другую.

110-вершинный граф Иванова — Иофиновой — полусимметричный кубический граф с 110 вершинами и 165 рёбрами.

Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным. Такие графы не часто встречаются. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976 и 1981 соответственно.

Граф Шрикханде — граф, найденный С. С. Шрикханде в 1959 году. Граф сильно регулярен, имеет 16 вершин и 48 рёбер и каждая вершина имеет степень 6. Каждая пара узлов имеет ровно два общих соседа, независимо от того, связана эта пара ребром или нет.

Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона.

Квадратичный граф — граф, в котором все вершины имеют степень 4. Другими словами, квадратичный граф является 4-регулярным графом.

3-регулярный граф Клейна — кубический граф с 56 вершинами и 84 рёбрами; назван по имени Феликса Клейна с двойственным ему 7-регулярным графом.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.