Interested Article - Клетка (теория графов)

Граф Петерсена
Граф Хивуда
Граф МакГи
Граф Татта — Коксетера
Граф Хоффмана — Синглтона

n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим , если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём.

Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными ). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее .

  • 3-клетка — К 4 , остов тетраэдра , 4 вершины.
  • 4-клетка — К 3,3 , один из двух минимальных не планарных графов, 6 вершин.
  • 5-клетка — Граф Петерсена , 10 вершин. Минимальный кубический граф с индексом самопересечения 2.
  • 6-клетка — Граф Хивуда , 14 вершин. Разбивается на 1-факторы (то есть, реберно раскрашиваем), любая сумма двух факторов образует гамильтонов цикл . Минимальный кубический граф с индексом самопересечения 3.
  • 7-клетка — Граф МакГи , 24 вершины. Минимальный кубический граф с индексом самопересечения 8.
  • 8-клетка — Граф Татта — Коксетера , 30 вершин.

Обобщённое определение

( r , n )-клетка — регулярный граф степени r (то есть из каждой вершины которого выходит ровно r рёбер) и обхвата n с наименьшим возможным числом вершин.

Тривиальные семейства

  • (2, n )-клетками являются, очевидно, циклические графы C n
  • ( r -1,3)-клетки — полные графы К r из r вершин
  • ( r ,4)-клетки — полные двудольные графы К r , r , у которых в каждой доле находится по r вершин

Нетривиальные представители

Известны ещё некоторые клетки. В таблице ниже показано количество вершин в ( r , n )-клетках степени 3≤ r ≤7 и обхвата 3≤ n ≤12. Клетки для этих и бо́льших r и n описаны здесь: (на английском языке).

n : 3 4 5 6 7 8 9 10 11 12
r = 3: 4 6 10 14 24 30 58 70 112 126
r = 4: 5 8 19 26 67 80 275 384 728
r = 5: 6 10 30 42 152 170 2730
r = 6: 7 12 40 62 294 312 7812
r = 7: 8 14 50 90

Графы Мура

Количество вершин в ( r , n )-клетке больше или равно

для нечётных n и
для чётных.

Если имеет место равенство, то соответствующий граф называется графом Мура . В то время как клетка существует для всяких r > 2 и n > 2, нетривиальных графов Мура гораздо меньше. Из вышеупомянутых клеток, графами Мура являются Граф Петерсена , граф Хивуда , граф Татта — Коксетера и граф Хоффмана — Синглтона. Доказано, что все нечётные случаи исчерпываются n = 5, r = 2, 3, 7 и, возможно, 57, а чётные n = 6, 8, 12.

Примечания

  1. Bannai, E. and Ito, T. «On Moore Graphs.» J. Fac. Sci. Univ. Tokyo Ser. A 20, 191—208, 1973
  2. Damerell, R. M. «On Moore Graphs.» Proc. Cambridge Philos. Soc. 74, 227—236, 1973
  3. Hoffman, A. J. and Singleton, R. R. «On Moore Graphs of Diameter 2 and 3.» IBM J. Res. Develop. 4, 497—504, 1960

Литература

Ссылки

  • Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
  • (англ.)
Источник —

Same as Клетка (теория графов)