Граф Мура

Граф Мура регулярний граф степеня і діаметра , число вершин якого дорівнює верхній межі

Еквівалентне визначення графа Мура — це граф діаметра з обхватом . Ще одне еквівалентне визначення графа Мура  — це граф із обхватом , що має рівно циклів довжини , де ,  — число вершин і ребер графа . Графи, фактично, екстремальні щодо числа циклів, довжина яких дорівнює обхвату графа[1].

Алан Гоффман і Роберт Сінглтон[2] назвали граф ім'ям Едварда Мура, який поставив питання опису та класифікації таких графів.

Маючи максимально можливе число вершин для заданої комбінації степеня і діаметра, графи Мура мають мінімально можливе число вершин для регулярних графів із заданими степенем і обхватом. Таким чином, будь-який граф Мура є кліткою[3]. Формулу для числа вершин графа Мура можна узагальнити для можливості визначення графів Мура з парним обхватом, і ці графи знову ж є клітками.

Межі числа вершин за степенем і діаметром

Граф Петерсена як граф Мура. Будь-яке дерево пошуку в ширину має вершин у його i-ому рівні.

Нехай  — будь-який граф із найбільшим степенем і діаметром , тоді візьмемо дерево, утворене пошуком у ширину, з коренем у вершині . Це дерево має 1 вершину рівня 0 (сама вершина ), і максимум вершин рівня 1 (сусіди вершини ). На наступному рівні є максимум вершин — кожен сусід вершини використовує одне ребро для з'єднання з вершиною , так що має максимум сусідів рівня 2. У загальному випадку подібні доводи показують, що на будь-якому рівні може бути не більше вершин. Таким чином, загальне число вершин може бути не більшим від

Гоффман і Сінглтон[2] спочатку визначили граф Мура як граф, для якого ця межа числа вершин досягається. Таким чином, будь-який граф Мура має максимально можливе число вершин серед усіх графів, у яких степінь не перевершує , а діаметр .

Пізніше Сінглтон[4] показав, що графи Мура можна еквівалентно визначити як граф, що має діаметр і обхват . Ці дві вимоги комбінуються, з чого виводиться d-регулярність графа для деякого .

Графи Мура як клітки

Замість верхньої межі числа вершин у графі в термінах його найбільшого степеня і діаметра ми можемо використовувати нижню межу числа вершин у термінах найменшого степеня і обхвату[3]. Припустимо, що граф має найменший степінь і обхват . Виберемо довільну початкову вершину і, як і раніше, уявимо дерево пошуку в ширину з коренем у . Це дерево повинне мати одну вершину рівня 0 (сама вершина ) і щонайменше вершин на рівні 1. На рівні 2 (для ), має бути щонайменше вершин, оскільки кожна вершина на рівні має щонайменше ще зв'язків, і ніякі дві вершини рівня 1 не можуть бути суміжними або мати спільні вершини рівня 2, оскільки утворився б цикл, коротший, ніж обхват. У загальному випадку схожі доводи показують, що на будь-якому рівні має бути принаймні вершин. Таким чином, загальне число вершин має бути не менше від

У графі Мура це число вершин досягається. Кожен граф Мура має обхват рівно  — він не має достатньо вершин, щоб мати більший обхват, а коротший цикл призвів би до нестачі вершин на перших рівнях деяких дерев пошуку в ширину. Таким чином, будь-який граф Мура має мінімально можливе число вершин серед усіх графів з мінімальним степенем і діаметром  — він є кліткою.

Для парного обхвату можна утворити аналогічне дерево пошуку в ширину, починаючи зі середини одного ребра. Отримуємо межу мінімального числа вершин у графі цього обхвату з мінімальним степенем

Таким чином, до графів Мура іноді відносять графи, на яких ця межа досягається. Знову ж, будь-який такий граф є кліткою.

Приклад

Теорема Гоффмана — Сінглтона стверджує, що будь-який граф Мура з обхватом 5 повинен мати степінь 2, 3, 7 або 57. Графами Мура є:

  • Повні графи з N > 2 вершинами (діаметр 1, обхват 3, степінь n-1, порядок ).
  • Непарний цикл (діаметр , обхват , степінь 2, порядок 2n+1).
  • Граф Петерсена (діаметр 2, обхват 5, степінь 3, порядок 10).
  • Граф Гоффмана-Сінглтона (діаметр 2, обхват 5, степінь 7, порядок 50).
  • Гіпотетичний граф з діаметром 2, обхватом 5, степенем 57 і порядком 3250, нині невідомо, чи такий існує.

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

В узагальненому визначенні графів Мура, де дозволяється парний обхват, графи з парним обхватом відповідають графам інцидентності (можливо вироджених) узагальнених багатокутників. Кілька прикладів — парні цикли , повні дводольні графи з обхватом чотири, граф Хівуда зі степенем 3 і обхватом 6 і граф Татта — Коксетера зі степенем 3 і обхватом 8. Відомо[5][6], що всі графи Мура, крім перерахованих вище, повинні мати обхват 5, 6, 8 або 12. Випадок парного обхвату випливає з теореми Фейта — Хіґмана про можливі значення для узагальнених n-кутників.

Див. також

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

Примітки

Література

  • Jernej Azarija, Sandi Klavžar. Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles // Journal of Graph Theory.  2015. Т. 80 (3 лютого). С. 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 (3 лютого). С. 191–208. Архівовано з джерела 24 квітня 2012.
  • R. M. Damerell. On Moore graphs // Mathematical Proceedings of the Cambridge Philosophical Society.  1973. Т. 74 (3 лютого). С. 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 (3 лютого). С. 215–235..
  • Alan J. Hoffman, Robert R. Singleton. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development.  1960. Т. 5, вип. 4 (3 лютого). С. 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 (3 лютого). С. 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 (3 лютого). С. 42–43. DOI:10.2307/2315106.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.