Граф Мура

Нерешенная задача по математике :

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

(еще нерешенные задачи по математике)

В теории графов граф Мура — это регулярный граф которого , обхват (длина наименьшего цикла ) более чем в два раза превышает его диаметр (расстояние между двумя самыми дальними вершинами ). Если степень такого графа равна d диаметр равен k , то его обхват должен быть равен 2k , а его + 1 . Это верно для графа степени d и диаметра k тогда и только тогда, когда число его вершин равно

$1+d\sum _{i=0}^{k-1}(d-1)^{i},$

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

Другое эквивалентное определение графа Мура G состоит в том, что он имеет обхват g = 2 k + 1 и точно n / g ( m – n + 1) циклов длины g , где n и m — соответственно количество вершин и ребер G . Фактически они экстремальны по отношению к числу циклов, длина которых равна обхвату графа.

Графы Мура были названы Хоффманом и Синглтоном (1960) в честь Эдварда Ф. Мура , который поставил вопрос об описании и классификации этих графов.

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

Ограничение вершин по степени и диаметру

Граф Петерсена как граф Мура. Любое дерево поиска в ширину имеет d ( d − 1) ^{я -1} вершины на своем i -м уровне для i ≥ 1 .

Пусть G — любой граф с максимальной степенью d и диаметром k , и рассмотрим дерево, сформированное поиском в ширину, начиная с любой вершины v . Это дерево имеет 1 вершину на уровне 0 ( сам v ) и не более d вершин на уровне 1 (соседи v ). На следующем уровне имеется не более d ( d − 1) вершин: каждый сосед v использует одну из своих смежностей для соединения с v и поэтому может иметь не более d − 1 соседей на уровне 2. В общем, аналогичный аргумент показывает, что на любом уровне 1 ≤ i ≤ k может быть не более d ( d − 1) ^{я -1} вершины. Таким образом, общее число вершин может быть не более

$1+d\sum _{i=0}^{k-1}(d-1)^{i}.$

Хоффман и Синглтон (1960) первоначально определили граф Мура как граф, для которого эта граница числа вершин соблюдается точно. Следовательно, любой граф Мура имеет максимально возможное количество вершин среди всех графов с максимальной степенью d и диаметром k .

Позже Синглтон (1968) показал, что графы Мура эквивалентно могут быть определены как имеющие диаметр k и обхват 2 k + 1 ; эти два требования в совокупности заставляют граф быть d -регулярным для некоторого d и удовлетворять формуле подсчета вершин.

Мура

Вместо верхней границы количества вершин в графе через его максимальную степень и диаметр, мы можем вычислить аналогичными методами нижнюю границу числа вершин через его минимальную степень и его обхват . Предположим, 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) ^я вершины. Таким образом, общее число вершин должно быть не менее

$1+d\sum _{i=1}^{k-1}(d-1)^{i}.$

В графе Мура эта граница количества вершин соблюдается точно. Каждый граф Мура имеет обхват ровно 2k мало + 1 : в нем недостаточно вершин, чтобы иметь больший обхват, а более короткий цикл приведет к тому, что на первых k уровнях некоторого дерева поиска в ширину будет слишком вершин .Следовательно, любой граф Мура имеет минимально возможное количество вершин среди всех графов с минимальной степенью d и обхватом 2 k + 1 : это клетка .

Для четного обхвата 2 k можно аналогичным образом сформировать дерево поиска в ширину, начиная с середины одного ребра. Результирующая оценка минимального числа вершин в графе этого обхвата минимальной степени d равна

$2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0}^{k-2}(d-1)^{i}.$

(Вместо этого правая часть формулы подсчитывает количество вершин в дереве поиска в ширину, начиная с одной вершины, с учетом возможности того, что вершина на последнем уровне дерева может быть смежной с d вершинами на предыдущем уровне. .)Таким образом, графы Мура иногда определяются как включающие графы, которые точно соответствуют этой границе. Опять же, любой такой граф должен быть клеткой.

Примеры

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

• Полные графы K _n на n > 2 узлах (диаметр 1, обхват 3, степень n − 1 , порядок n )
• Нечетные циклы C _{2 n +1} (диаметр n , обхват 2 n + 1 , степень 2, порядок 2 n + 1 )
• Граф Петерсена (диаметр 2, обхват 5, степень 3, порядок 10)
• Граф Хоффмана – Синглтона (диаметр 2, обхват 5, степень 7, порядок 50)
• Гипотетический граф (или более одного) диаметра 2, обхвата 5, степени 57 и порядка 3250, существование которого неизвестно.

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

Если используется обобщенное определение графов Мура, которое допускает графы четного обхвата, графы Мура четного обхвата соответствуют графам инцидентности (возможных вырожденных) обобщенных многоугольников . Некоторыми примерами являются четные циклы C _{2 n} , полные двудольные графы K _{n , n} с обхватом четыре, граф Хивуда со степенью 3 и обхватом 6 и граф Тутта-Коксетера со степенью 3 и обхватом 8. В более общем смысле, это Известно, что, кроме перечисленных выше графов, все графы Мура должны иметь обхват 5, 6, 8 или 12. Случай четного обхвата также следует из теоремы Фейта-Хигмана о возможных значениях n для обобщенного n -угольника.

См. также

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

Ссылки

• Азария, Джерней; Клавжар, Сэнди (2015), «Графы и циклы Мура являются экстремальными графами для выпуклых циклов», Journal of Graph Theory , 80 : 34–42, arXiv : 1210.6342 , doi : 10.1002/jgt.21837 , S2CID   333785
• Баннаи, Э.; Ито, Т. (1973), «О конечных графах Мура» , Журнал факультета естественных наук Токийского университета. Секта. 1 А, Математика , 20 : 191–208, MR   0323615 , заархивировано из оригинала 24 апреля 2012 г.
• Боллобас, Бела (1998), Современная теория графов , Тексты для аспирантов по математике , том. 184, Шпрингер-Верлаг .
• Дальфо, К. (2019), «Обзор недостающего графа Мура» (PDF) , Линейная алгебра и ее приложения , 569 : 1–14, doi : 10.1016/j.laa.2018.12.035 , hdl : 2117/127212 , МР   3901732 , S2CID   126689579
• Дамерелл, Р.М. (1973), «О графах Мура», Mathematical Proceedings of the Cambridge Philosophical Society , 74 (2): 227–236, Bibcode : 1973PCPS...74..227D , doi : 10.1017/S0305004100048015 , MR   0318004
• Эрдос, Пол ; Реньи, Альфред ; Сос, Вера Т. (1966), «Об одной задаче теории графов» (PDF) , Studia Sci. Венгерский. , 1 : 215–235, заархивировано из оригинала (PDF) 9 марта 2016 г. , получено 23 февраля 2010 г.
• Хоффман, Алан Дж .; Синглтон, Роберт Р. (1960), «Графы Мура диаметром 2 и 3», IBM Journal of Research and Development , 5 (4): 497–504, doi : 10.1147/rd.45.0497 , MR   0140437
• Мачай, Мартин; Ширань, Йозеф (2010), «Поиск свойств отсутствующего графа Мура», Линейная алгебра и ее приложения , 432 (9): 2381–2398, doi : 10.1016/j.laa.2009.07.018 .
• Синглтон, Роберт Р. (1968), «Нерегулярного графа Мура не существует», American Mathematical Monthly , 75 (1): 42–43, doi : 10.2307/2315106 , JSTOR   2315106 , MR   0225679

Внешние ссылки

• Брауэр и Хемерс: Спектры графов
• Вайсштейн, Эрик В. , « Граф Мура » (« Теорема Хоффмана-Синглтона ») в MathWorld .