Граф Мерингера

Граф Мерингера — это 5-регулярный неориентированный граф с 30 вершинами и 75 рёбрами[1][2]. Граф является одной из четырёх (5,5)-клеток, другие три — клетка Фостера, граф Робертсона — Вегнера и граф Вонга. Граф назван именем Маркуса Мерингера, открывшего его в 1999, хотя он долгое время считал, что только три подобных графа существует.

Граф Мерингера

Граф Мерингера
Назван в честь Маркуса Мерингера
Вершин 30
Рёбер 75
Диаметр 3
Обхват 5
Автоморфизмы 96
Хроматическое число 3
Хроматический индекс 5
Свойства Клетка

Граф имеет хроматическое число 3, диаметр 3 и он вершинно 5-связен.

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

Характеристический многочлен графа равен

Литература

  1. Weisstein, Eric W. Meringer Graph (англ.) на сайте Wolfram MathWorld.
  2. Markus Meringer. Fast generation of regular graphs and construction of cages // Journal of Graph Theory. — 1999. Т. 30, вып. 2. С. 137–146. doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.