Существует ли граф Мура с обхватом 5 и степенью 57?
В теории графов граф Мура — это регулярный граф, обхват которого (длина наименьшего цикла ) более чем в два раза превышает его диаметр (расстояние между двумя самыми дальними вершинами ). Если степень такого графа равна d , а его диаметр равен k , то его обхват должен быть равен 2k + 1 . Это верно для графа степени d и диаметра k тогда и только тогда, когда число его вершин равно
верхняя граница наибольшего возможного числа вершин в любом графе этой степени и диаметра. Таким образом, эти графы решают проблему градусного диаметра для своих параметров.
Другое эквивалентное определение графа Мура G состоит в том, что он имеет обхват g = 2 k + 1 и точнон/г( m – n + 1) циклов длины g , где n и m — соответственно количество вершин и ребер G . Фактически они экстремальны по числу циклов, длина которых равна обхвату графа. [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 вершин. Таким образом, общее число вершин должно быть не менее
В графе Мура эта граница количества вершин соблюдается точно. Каждый граф Мура имеет обхват ровно 2k + 1 : в нем недостаточно вершин для большего обхвата, а более короткий цикл приведет к тому , что на первых k уровнях некоторого дерева поиска в ширину будет слишком мало вершин . Следовательно, любой граф Мура имеет минимально возможное количество вершин среди всех графов с минимальной степенью d и обхватом 2 k + 1 : это клетка .
Для четного обхвата 2 k можно аналогичным образом сформировать дерево поиска в ширину, начиная с середины одного ребра. Результирующая оценка минимального числа вершин в графе этого обхвата минимальной степени d равна
(Вместо этого правая часть формулы подсчитывает количество вершин в дереве поиска в ширину, начиная с одной вершины, с учетом возможности того, что вершина на последнем уровне дерева может быть смежной с d вершинами на предыдущем уровне. .) Таким образом, графы Мура иногда определяются как включающие графы, которые точно соответствуют этой границе. Опять же, любой такой граф должен быть клеткой.
Теорема Хоффмана -Синглтона утверждает, что любой граф Мура с обхватом 5 должен иметь степень 2, 3, 7 или 57. Графы Мура: [3]
Хотя все известные графы Мура являются вершинно-транзитивными графами , неизвестный граф (если он существует) не может быть вершинно-транзитивным, поскольку его группа автоморфизмов может иметь порядок не более 375, что меньше количества его вершин. [5]
Если используется обобщенное определение графов Мура, которое допускает графы четного обхвата, графы Мура четного обхвата соответствуют графам инцидентности (возможных вырожденных) обобщенных многоугольников . Некоторыми примерами являются четные циклы C 2 n , полные двудольные графы K n , n с обхватом четыре, граф Хивуда со степенью 3 и обхватом 6 и граф Тутта-Коксетера со степенью 3 и обхватом 8. В более общем смысле, это известно, что, кроме перечисленных выше графов, все графы Мура должны иметь обхват 5, 6, 8 или 12. [6] Случай четного обхвата также следует из теоремы Фейта-Хигмана о возможных значениях n для обобщенного n - гон.
