Граф Фолкмана (Ijgs Skltbgug)
Граф Фолкмана | |
---|---|
| |
Назван в честь | Дж. Фолкмана |
Вершин | 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].
Как полусимметричный граф, граф Фолкмана является двудольным и его группа автоморфизмов действует транзитивно на каждую долю вершин двудольного графа. На диаграмме ниже, показывающей хроматическое число графа, зелёные вершины не могут быть отражены в красные каким-либо автоморфизмом, но любая красная вершина может быть отражена в любую другую красную вершину, а любая зелёная — в любую другую зелёную вершину.
Характеристический многочлен графа Фолкмана равен .
Галерея
[править | править код]-
Хроматический индекс графа Фолкмана равен 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.
Для улучшения этой статьи желательно:
|