Существует ли граф Мура с обхватом 5 и степенью 57?
В теории графов , А граф Мур является регулярным графом по степени г и диаметром к которой число вершин равна верхней грани
Эквивалентное определение графа Мура состоит в том, что это граф диаметра с обхватом . Другое эквивалентное определение графа Мура состоит в том, что он имеет обхват и точно циклы длины , где и - соответственно числа вершин и ребер графа . Фактически они экстремальны по отношению к числу циклов, длина которых равна обхвату графа. [1]
Графы Мура были названы Хоффманом и Синглтоном (1960) в честь Эдварда Ф. Мура , который поставил вопрос об описании и классификации этих графов.
Помимо максимально возможного количества вершин для данной комбинации степени и диаметра, графы Мура имеют минимально возможное количество вершин для обычного графа с данной степенью и обхватом. То есть любой граф Мура - это клетка . [2] Формула для числа вершин в графе Мура может быть обобщена, чтобы позволить определение графов Мура с четным и нечетным обхватом, и снова эти графы являются клетками.
Пусть G - любой граф с максимальной степенью d и диаметром k , и рассмотрим дерево, образованное поиском в ширину, начиная с любой вершины v . Это дерево имеет 1 вершину на уровне 0 ( сама v ) и не более d вершин на уровне 1 (соседи v ). На следующем уровне имеется не более d ( d -1) вершин: каждый сосед v использует одну из своих смежностей для соединения с v и, таким образом, может иметь не более d -1 соседей на уровне 2. В общем, аналогичный аргумент показывает, что на любом уровне 1 ≤ i ≤k может быть не более d ( d -1) i-1 вершин. Таким образом, общее количество вершин может быть не более
Хоффман и Синглтон (1960) первоначально определили граф Мура как граф, для которого точно соблюдается это ограничение на количество вершин. Следовательно, любой граф Мура имеет максимально возможное количество вершин среди всех графов максимальной степени d и диаметра k .
Позже Синглтон (1968) показал, что графы Мура могут быть эквивалентно определены как имеющие диаметр k и обхват 2 k +1; эти два требования объединяются, чтобы заставить граф быть d -регулярным для некоторого d и удовлетворять формуле подсчета вершин.
Вместо верхней границы числа вершин в графе с точки зрения его максимальной степени и диаметра, мы можем вычислить с помощью аналогичных методов нижнюю оценку количества вершин с точки зрения его минимальной степени и его обхвата . [2] Предположим, что G имеет минимальную степень d и обхват 2 k +1. Выбираем произвольно начальную вершину v и, как и раньше, рассмотрим дерево поиска в ширину с корнем в v . Это дерево должно иметь одну вершину на уровне 0 ( само v ) и не менее d вершин на уровне 1. На уровне 2 (при k > 1) должно быть не менее d ( d-1) вершин, потому что каждая вершина на уровне 1 имеет по крайней мере d -1 оставшихся смежностей для заполнения, и никакие две вершины на уровне 1 не могут быть смежными друг с другом или с общей вершиной на уровне 2, потому что это создаст цикл короче. чем предполагаемый обхват. В общем, аналогичные рассуждения показывают, что на любом уровне 1 ≤ i ≤ k должно быть не менее d ( d -1) i вершин. Таким образом, общее количество вершин должно быть не менее
В графе Мура эта граница на количество вершин выполняется точно. Каждый граф Мура имеет обхват ровно 2 k +1: у него недостаточно вершин, чтобы иметь более высокий обхват, а более короткий цикл приведет к тому, что на первых k уровнях некоторого дерева поиска в ширину будет слишком мало вершин . Следовательно, любой граф Мура имеет минимально возможное количество вершин среди всех графов с минимальной степенью d и диаметром k : это клетка .
Для четного обхвата 2 k аналогичным образом можно сформировать дерево поиска в ширину, начиная с середины одного ребра. Результирующая оценка минимального числа вершин в графе этого обхвата с минимальной степенью d равна
(Правая часть формулы вместо этого подсчитывает количество вершин в дереве поиска в ширину, начиная с одной вершины, учитывая возможность того, что вершина на последнем уровне дерева может быть смежной с d вершинами на предыдущем уровне .) Таким образом, графы Мура иногда определяются как включающие графы, которые точно соответствуют этой границе. Опять же, любой такой граф должен быть клеткой.
Теорема Хоффмана – Синглтона утверждает, что любой граф Мура с обхватом 5 должен иметь степень 2, 3, 7 или 57. Графы Мура: [3]
Хотя все известные графы Мура являются вершинно-транзитивными графами , неизвестный (если он существует) не может быть вершинно-транзитивным, так как его группа автоморфизмов может иметь порядок не более 375, что меньше его числа вершин. [5]
Если используется обобщенное определение графов Мура, которое допускает четные графы с обхватом, то четные графы Мура соответствуют графам инцидентности (возможных вырожденных) обобщенных многоугольников . Некоторыми примерами являются четные циклы , полные двудольные графы с обхватом четыре, граф Хивуда со степенью 3 и обхватом 6 и граф Тутта – Кокстера со степенью 3 и обхватом 8. В целом известно, что кроме графов Из перечисленных выше все графы Мура должны иметь обхват 5, 6, 8 или 12. [6] Случай четного обхвата также следует из теоремы Фейта-Хигмана о возможных значениях n для обобщенного n-угольника.