Граф Мура

Нерешённые проблемы математики: Существует ли граф Мура с обхватом 5 и степенью 57?

Граф Мура — регулярный граф степени [math]\displaystyle{ d }[/math] и диаметром [math]\displaystyle{ k }[/math], число вершин которого равно верхней границе

[math]\displaystyle{ 1+d\sum_{i=0}^{k-1}(d-1)^i . }[/math]

Эквивалентное определение графа Мура — это граф диаметра [math]\displaystyle{ k }[/math] с обхватом [math]\displaystyle{ 2k+1 }[/math]. Ещё одно эквивалентное определение графа Мура [math]\displaystyle{ G }[/math] — это граф с обхватом [math]\displaystyle{ g=2k+1 }[/math], имеющий в точности [math]\displaystyle{ \frac{n}{g}(m-n+1) }[/math] циклов длины [math]\displaystyle{ g }[/math], где [math]\displaystyle{ n }[/math], [math]\displaystyle{ m }[/math] — число вершин и рёбер графа [math]\displaystyle{ G }[/math]. Графы, фактически, экстремальны по отношению к числу циклов, длина которых равна обхвату графа.

Графы названы Аланом Хоффманом и Робертом Синглтоном именем Эдварда Мура, который поставил вопрос описания и классификации таких графов.

Имея максимально возможное число вершин для заданной комбинации степени и диаметра, графы Мура имеют минимально возможное число вершин для регулярных графов с заданной степенью и обхватом. Таким образом, любой граф Мура является клеткой. Формула для числа вершин графа Мура может быть обобщена для возможности определения графов Мура с чётным обхватом, и эти графы снова являются клетками.

Границы числа вершин по степени и диаметру

Граф Петерсена как граф Мура. Любое дерево поиска в ширину имеет [math]\displaystyle{ d(d-1)^i }[/math] вершин в его i-ом уровне.

Пусть [math]\displaystyle{ G }[/math] — любой граф с максимальной степенью [math]\displaystyle{ d }[/math] и диаметром [math]\displaystyle{ k }[/math], тогда возьмём дерево, образованное поиском в ширину, с корнем в вершине [math]\displaystyle{ v }[/math]. Это дерево имеет 1 вершину уровня 0 (сама вершина [math]\displaystyle{ v }[/math]), и максимум [math]\displaystyle{ d }[/math] вершин уровня 1 (соседи вершины [math]\displaystyle{ v }[/math]). На следующем уровне имеется максимум [math]\displaystyle{ d(d-1) }[/math] вершин — каждый сосед вершины [math]\displaystyle{ v }[/math] использует одно ребро для соединения с вершиной [math]\displaystyle{ v }[/math], так что имеет максимум [math]\displaystyle{ d-1 }[/math] соседей уровня 2. В общем случае подобные доводы показывают, что на любом уровне [math]\displaystyle{ 1\leq{i}\leq{k} }[/math] может быть не больше [math]\displaystyle{ d(d-1)^i }[/math] вершин. Таким образом, общее число вершин может быть не больше

[math]\displaystyle{ 1+d\sum_{i=0}^{k-1}(d-1)^i. }[/math]

Хоффман и Синглтон первоначально определили граф Мура как граф, для которого эта граница числа вершин достигается. Таким образом, любой граф Мура имеет максимально возможное число вершин среди всех графов, в которых степень не превосходит [math]\displaystyle{ d }[/math], диаметр — [math]\displaystyle{ k }[/math].

Позднее Синглтон показал, что графы Мура можно эквивалентно определить как граф, имеющий диаметр [math]\displaystyle{ k }[/math] и обхват [math]\displaystyle{ 2k-1 }[/math]. Эти два требования комбинируются, из чего выводится d-регулярность графа для некоторого [math]\displaystyle{ d }[/math].

Графы Мура в качестве клеток

Вместо верхней границы числа вершин в графе в терминах его максимальной степени и диаметра мы можем использовать нижнюю границу числа вершин в терминах минимальной степени и обхвата . Предположим, что граф [math]\displaystyle{ G }[/math] имеет минимальную степень [math]\displaystyle{ d }[/math] и обхват [math]\displaystyle{ 2k+1 }[/math]. Выберем произвольную начальную вершину [math]\displaystyle{ v }[/math] и, как и прежде, представим дерево поиска в ширину с корнем в [math]\displaystyle{ v }[/math]. Это дерево должно иметь одну вершину уровня 0 (сама вершина [math]\displaystyle{ v }[/math]) и по меньшей мере [math]\displaystyle{ d }[/math] вершин на уровне 1. На уровне 2 (для [math]\displaystyle{ k \gt 1 }[/math]), должно быть по меньшей мере [math]\displaystyle{ d(d-1) }[/math] вершин, поскольку каждая вершина на уровне [math]\displaystyle{ l }[/math] имеет по меньшей мере [math]\displaystyle{ d-1 }[/math] оставшихся связей, и никакие две вершины уровня 1 не могут быть смежными или иметь общие вершины уровня 2, поскольку создался бы цикл, более короткий, чем обхват. В общем случае похожие доводы показывают, что на любом уровне [math]\displaystyle{ 1\leq{i}\leq{k} }[/math] должно быть по меньшей мере [math]\displaystyle{ d(d-1)^i }[/math] вершин. Таким образом, общее число вершин должно быть не менее

[math]\displaystyle{ 1+d\sum_{i=0}^{k-1}(d-1)^i. }[/math]

В графе Мура это число вершин достигается. Каждый граф Мура имеет обхват в точности [math]\displaystyle{ 2k+1 }[/math] — он не имеет достаточно вершин, чтобы иметь больший обхват, а более короткий цикл привёл бы к недостатку вершин в первых [math]\displaystyle{ k }[/math] уровнях некоторых деревьев поиска в ширину. Таким образом, любой граф Мура имеет минимально возможное число вершин среди всех графов с минимальной степенью [math]\displaystyle{ d }[/math] и диаметром [math]\displaystyle{ k }[/math] — он является клеткой.

Для чётного обхвата [math]\displaystyle{ 2k }[/math] можно образовать аналогичное дерево поиска в ширину, начиная с середины одного ребра. Получаем границу минимального числа вершин в графе этого обхвата с минимальной степенью [math]\displaystyle{ d }[/math]

[math]\displaystyle{ 2\sum_{i=0}^{k-1}(d-1)^i=1+(d-1)^{k-1}+d\sum_{i=0}^{k-2}(d-1)^i. }[/math]

Таким образом, в графы Мура иногда включаются графы, на которых данная граница достигается. Снова любой такой граф является клеткой.

Примеры

Теорема Хоффмана — Синглтона утверждает, что любой граф Мура с обхватом 5 должен иметь степень 2, 3, 7 или 57. Графами Мура являются:

• Полные графы [math]\displaystyle{ K_n }[/math] с n > 2 вершинами. (диаметр 1, обхват 3, степень n-1, порядок [math]\displaystyle{ n }[/math])
• Нечётные циклы [math]\displaystyle{ C_{2n+1} }[/math]. (диаметр [math]\displaystyle{ n }[/math], обхват [math]\displaystyle{ 2n+1 }[/math], степень 2, порядок 2n+1)
• Граф Петерсена. (диаметр 2, обхват 5, степень 3, порядок 10)
• Граф Хоффмана — Синглтона. (диаметр 2, обхват 5, степень 7, порядок 50)
• Гипотетический граф с диаметром 2, обхватом 5, степенью 57 и порядком 3250, в настоящее время неизвестно, существует ли такой.

Хигман показал, что, в отличие от других графов Мура, неизвестный граф не может быть вершинно-транзитивным. Мачай и Ширан позднее показали, что порядок автоморфизмов такого графа не превосходит 375.

В обобщённом определении графов Мура, где разрешается чётный обхват, графы с чётным обхватом соответствуют графам инцидентности (возможно вырожденных) обобщённых многоугольников. Несколько примеров — чётные циклы [math]\displaystyle{ C_{2n} }[/math], полные двудольные графы [math]\displaystyle{ K_{n,n} }[/math] с обхватом четыре, граф Хивуда со степенью 3 и обхватом 6 и граф Татта — Коксетера со степенью 3 и обхватом 8. Известно), что все графы Мура, кроме перечисленных выше, должны иметь обхват 5, 6, 8 или 12. Случай чётного обхвата следует из теоремы Фейта-Хигмана о возможных значениях [math]\displaystyle{ n }[/math] для обобщённых n-угольников.

См. также

• Проблема размера — диаметра
• Таблица наибольших известных графов для заданного диаметра и максимальной степени

Литература

• Jernej Azarija, Sandi Klavžar. Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles // Journal of Graph Theory. — 2015. — Т. 80. — С. 34–42. — doi:10.1002/jgt.21837.
• Béla Bollobás. Modern graph theory. — Springer-Verlag, 1998. — Т. 184. — (Graduate Texts in Mathematics)..
• E. Bannai, T. Ito. On finite Moore graphs // Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics. — 1973. — Т. 20. — С. 191–208. Архивировано 24 апреля 2012 года.
• R. M. Damerell. On Moore graphs // Mathematical Proceedings of the Cambridge Philosophical Society. — 1973. — Т. 74. — С. 227–236. — doi:10.1017/S0305004100048015.
• Paul Erdős, Alfréd Rényi, Vera T. Sós. On a problem of graph theory // Studia Sci. Math. Hungar.. — 1966. — Т. 1. — С. 215–235..
• Alan J. Hoffman, Robert R. Singleton. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development. — 1960. — Т. 5, вып. 4. — С. 497–504. — doi:10.1147/rd.45.0497.
• Martin Mačaj, Jozef Širáň. Search for properties of the missing Moore graph // Linear Algebra and its Applications. — 2010. — Т. 432. — С. 2381–2398. — doi:10.1016/j.laa.2009.07.018..
• Robert R. Singleton. There is no irregular Moore graph // American Mathematical Monthly. — 1968. — Т. 75, вып. 1. — С. 42–43. — doi:10.2307/2315106.

Ссылки

• Brouwer and Haemers: Spectra of graphs Архивная копия от 3 октября 2017 на Wayback Machine
• Weisstein, Eric W. Moore Graph (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Hoffman-Singleton Theorem (англ.) на сайте Wolfram MathWorld.