Степень вершины (теория графов)
- 1 year ago
- 0
- 0
n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим , если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём.
Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными ). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее .
( r , n )-клетка — регулярный граф степени r (то есть из каждой вершины которого выходит ровно r рёбер) и обхвата n с наименьшим возможным числом вершин.
Тривиальные семейства
Нетривиальные представители
Известны ещё некоторые клетки. В таблице ниже показано количество вершин в ( 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 )-клетке больше или равно
Если имеет место равенство, то соответствующий граф называется графом Мура . В то время как клетка существует для всяких r > 2 и n > 2, нетривиальных графов Мура гораздо меньше. Из вышеупомянутых клеток, графами Мура являются Граф Петерсена , граф Хивуда , граф Татта — Коксетера и граф Хоффмана — Синглтона. Доказано, что все нечётные случаи исчерпываются n = 5, r = 2, 3, 7 и, возможно, 57, а чётные n = 6, 8, 12.