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)-клетками являются, очевидно, циклические графы Cn (r-1,3)-клетки — полные графы Кr из r вершин (r,4)-клетки — полные двудольные графы Кr,r, у которых в каждой доле находится по r вершин Нетривиальные представители (7,5)-клетка — Граф Хоффмана — Синглтона, 50 вершин.
Известны ещё некоторые клетки. В таблице ниже показано количество вершин в (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, нетривиальных графов Мура гораздо меньше. Из вышеупомянутых клеток, графами Мура являются Граф Петерсена, граф Хивуда, граф Татта — Коксетера и граф Хоффмана — Синглтона. Доказано,Bannai, E. and Ito, T. «On Moore Graphs.» J. Fac. Sci. Univ. Tokyo Ser. A 20, 191—208, 1973Damerell, R. M. «On Moore Graphs.» Proc. Cambridge Philos. Soc. 74, 227—236, 1973Hoffman, A. J. and Singleton, R. R. «On Moore Graphs of Diameter 2 and 3.» IBM J. Res. Develop. 4, 497—504, 1960 что все нечётные случаи исчерпываются n = 5, r = 2, 3, 7 и, возможно, 57, а чётные n = 6, 8, 12.
Примечания
Литература Ф. Харари Теория графов. — : УРСС, — 2003. — 300 с — ISBN 5-354-00301-6.
Ссылки
https://web.archive.org/web/20090224031515/http://people.csse.uwa.edu.au/gordon/cages/
Категория:Теория графов Категория:Семейства графов