Таблица простых кубических графов

Связные 3-регулярные ( кубические ) простые графы перечислены для малых чисел вершин.

Возможности подключения

Число связных простых кубических графов на 4, 6, 8, 10,... вершинах равно 1, 2, 5, 19,... (последовательность A002851 в OEIS ). Классификация по связности ребер производится следующим образом: 1-связные и 2-связные графы определяются как обычно. При этом остальные графы остаются в 3-связном классе, поскольку каждый3-регулярный граф можно разбить, разрезав все ребра, примыкающие к любой из вершин. Чтобы уточнить это определение в свете алгебры связи угловых моментов (см. ниже), полезно подразделение 3-связных графов. Мы позвоним

Нетривиально 3-связные те, которые можно разбить тремя разрезами ребер на подграфы, в каждой части которых осталось не менее двух вершин.
Циклически 4-связные — все не 1-связные, не 2-связные и не нетривиально 3-связные.

Это объявляет числа 3 и 4 в четвертом столбце таблиц ниже.

Картинки

Шариковые модели графиков в другом столбцеВ таблице показаны вершины и ребра в стилеизображения молекулярных связей.Комментарии к отдельным фотографиям содержат обхват , диаметр , индекс Винера , Индекс Эстрады и индекс Кирхгофа . Aut — порядок группы автоморфизмов графа.Гамильтонова схема (если она присутствует) обозначается перечислением вершин.по этому пути от 1 вверх.(Положения вершин были определены путем минимизации парного потенциала, определяемого квадратом разности евклидова расстояния и теоретического расстояния графа, помещенного в Molfile , а затем визуализированного Jmol .)

Обозначение LCF

Обозначение LCF — это обозначение Джошуа Ледерберга , Коксетера и Фрухта для представления кубических графов , которые являются гамильтоновыми .

Два ребра цикла, примыкающие к какой-либо из вершин, не записываются.

Пусть $v$ — вершины графа, и опишите гамильтонову окружность вдоль $p$ вершин последовательностью ребер $v 0 v 1, v 1 v 2, ...,v p-2 v p-1, v p-1 v 0$ . Остановившись в вершине $vi vj$ , существует одна уникальная вершина $d расстоянии$ i , $соединенная хордой$ с $vi на$ ,

j=i+d_{i}\quad ({\bmod {\,}}p),\quad 2\leq d_{i}\leq p-2.

Вектор $[d 0, d 1, ..., d p-1]$ из $p$ целых чисел является подходящим, хотя и не единственным, представлением кубического графа Гамильтона. Это дополняется двумя дополнительными правилами:

Если a $d i > p/2$ , замените его на $d i - p$ ;
избегайте повторения последовательности $d i,$ если они периодические, и замените их экспоненциальной записью.

Поскольку начальная вершина пути не имеет значения, числа в представлении можно переставлять циклически. Если граф содержит разные гамильтоновы схемы, можно выбрать одну из них, чтобы разместить обозначения. Один и тот же граф может иметь разные обозначения LCF, в зависимости от того, как именно расположены вершины.

Часто антипалиндромные представления с

d_{p-1-i}=-d_{i}\quad ({\bmod {\,}}p),\quad i=0,1,\ldots p/2-1

являются предпочтительными (если они существуют), а лишняя часть заменяется точкой с запятой и тире «; –». Обозначение LCF $[5, -9, 7, -7, 9, -5] 4$ , например, и на этом этапе будет сокращен до $[5, -9, 7; -] 4$ .

Стол

4 вершины

тихий.	обхват	Или	соединять.	LCF	имена	картина
1	3	24	4	[2] ⁴	К ₄	4 вершины и 6 ребер. График Юциса символа 6-j

6 вершин

тихий.	обхват	Или	соединять.	LCF	имена	картина
2	3	12	3	[2, 3, −2] ²	призменный график Y ₃	6 вершин и 9 ребер
2	4	72	4	[3] ⁶	К _{3, 3} , график полезности	6 вершин и 9 ребер. Граф Юциса символа 9-j .

8 вершин

тихий.	обхват	Или	соединять.	LCF	имена	картинки
3	3	16	2	[2, 2, −2, −2] ²		8 вершин и 12 ребер
3	3	4	3	[4, −2, 4, 2] ² или [2, 3, −2, 3; –]		8 вершин и 12 ребер
2	3	12	3	[2, 4, −2, 3, 3, 4, −3, −3]		8 вершин и 12 ребер
3	4	48	4	[−3, 3] ⁴	кубический граф	8 вершин и 12 ребер. Граф Юциса 12j-символа второго рода.
2	4	16	4	[4] ⁸ или [4, −3, 3, 4] ²	Граф Вагнера	8 вершин и 12 ребер. Граф Юциса 12j-символа первого рода.

10 вершин

тихий.	обхват	Или	соединять.	LCF	имена	картинки
5	3	32	1		Список краев 0–1, 0–6, 0–9, 1–2, 1–5, 2–3, 2–4, 3–4, 3–5, 4–5, 6–7, 6–8, 7–8, 7–9, 8–9	10 вершин и 15 ребер
4	3	4	2	[4, 2, 3, −2, −4, −3, 2, 2, −2, −2]
3	3	8	2	[2, −3, −2, 2, 2; –]
3	3	16	2	[−2, −2, 3, 3, 3; –]
4	3	16	2	[2, 2, −2, −2, 5] ²
3	3	2	3	[2, 3, −2, 5, −3] ² [3, −2, 4, −3, 4, 2, −4, −2, −4, 2]
3	3	12	3	[2, −4, −2, 5, 2, 4, −2, 4, 5, −4]		10 вершин и 15 ребер
3	3	2	3	[5, 3, 5, −4, −3, 5, 2, 5, −2, 4] [−4, 2, 5, −2, 4, 4, 4, 5, −4, −4] [−3, 2, 4, −2, 4, 4, −4, 3, −4, −4]		10 вершин и 15 ребер
3	3	4	3	[−4, 3, 3, 5, −3, −3, 4, 2, 5, −2] [3, −4, −3, −3, 2, 3, −2, 4, −3, 3]
3	3	6	3	[3, −3, 5, −3, 2, 4, −2, 5, 3, −4]
3	3	4	3	[2, 3, −2, 3, −3; –] [−4, 4, 2, 5, −2] ²
3	3	6	3	[5, −2, 2, 4, −2, 5, 2, −4, −2, 2]
3	3	8	3	[2, 5, −2, 5, 5] ² [2, 4, −2, 3, 4; –]		10 вершин и 15 ребер
3	4	48	3	[5, −3, −3, 3, 3] ²
3	4	8	4	[5, −4, 4, −4, 4] ² [5, −4, −3, 3, 4, 5, −3, 4, −4, 3]		Граф Юциса 15j-символа третьего рода.
3	4	4	4	[5, −4, 4, 5, 5] ² [−3, 4, −3, 3, 4; –] [4, −3, 4, 4, −4; –] [−4, 3, 5, 5, −3, 4, 4, 5, 5, −4]		Граф Юциса 15j-символа четвертого рода.
3	4	20	4	[5] ¹⁰ [−3, 3] ⁵ [5, 5, −3, 5, 3] ²		Граф Юциса 15j-символа первого рода.
3	4	20	4	[−4, 4, −3, 5, 3] ²	Пятиугольная призма , G _{5, 2}	Граф Юциса 15j-символа второго рода.
2	5	120	4		график Петерсена	Граф Юциса 15j-символа пятого рода.

12 вершин

тихий.	обхват	Или	соединять.	LCF	имена	картина
6	3	16	1		Список краев 0–1, 0–2, 0–11, 1–2, 1–6, 2–3, 3–4, 3–5, 4–5, 4–6, 5–6, 7–8, 7–9, 7–11, 8–9, 8–10, 9–10, 10–11
5	3	16	1		Список краев 0–1, 0–6, 0–11, 1–2, 1–3, 2–3, 2–5, 3–4, 4–5, 4–6, 5–6, 7–8, 7–9, 7–11, 8–9, 8–10, 9–10, 10–11
6	3	8	1		Список краев 0–1, 0–3, 0–11, 1–2, 1–6, 2–3, 2–5, 3–4, 4–5, 4–6, 5–6, 7–8, 7–9, 7–11, 8–9, 8–10, 9–10, 10–11
5	3	32	1		Список краев 0–1, 0–6, 0–11, 1–2, 1–4, 2–3, 2–5, 3–4, 3–6, 4–5, 5–6, 7–8, 7–9, 7–11, 8–9, 8–10, 9–10, 10–11
5	3	4	2	[3, −2, −4, −3, 4, 2] ² [4, 2, 3, −2, −4, −3; –]
4	3	8	2	[3, −2, −4, −3, 3, 3, 3, −3, −3, −3, 4, 2]
4	3	4	2	[4, 2, 3, −2, −4, −3, 2, 3, −2, 2, −3, −2]
4	4	64	2	[3, 3, 3, −3, −3, −3] ²
4	3	16	2	[2, −3, −2, 3, 3, 3; –]
4	3	16	2	[2, 3, −2, 2, −3, −2] ²
4	3	2	2	[−2, 3, 6, 3, −3, 2, −3, −2, 6, 2, 2, −2] [4, 2, −4, −2, −4, 6, 2, 2, −2, −2, 4, 6]
4	3	8	2	[6, 3, 3, 4, −3, −3, 6, −4, 2, 2, −2, −2]
5	3	4	2	[4, 2, 3, −2, −4, −3, 5, 2, 2, −2, −2, −5]
4	3	16	2	[−3, −3, −3, 5, 2, 2; –]
4	3	8	2	[2, −3, −2, 5, 2, 2; –]
4	3	4	2	[2, 4, −2, 3, −5, −4, −3, 2, 2, −2, −2, 5] [5, 2, −4, −2, −5, −5, 2, 2, −2, −2, 4, 5]
4	3	4	2	[−2, −2, 4, 4, 4, 4; –] [3, −4, −4, −3, 2, 2; –] [5, 3, 4, 4, −3, −5, −4, −4, 2, 2, −2, −2]
4	3	2	2	[4, −2, 4, 2, −4, −2, −4, 2, 2, −2, −2, 2] [5, −2, 2, 3, −2, −5, −3, 2, 2, −2, −2, 2]
5	3	16	2	[2, 2, −2, −2, −5, 5] ²
4	3	8	2	[−2, −2, 4, 5, 3, 4; –]
4	3	4	2	[5, 2, −3, −2, 6, −5, 2, 2, −2, −2, 6, 3]
4	3	8	2	[4, −2, 3, 3, −4, −3, −3, 2, 2, −2, −2, 2]
4	3	8	2	[−2, −2, 5, 3, 5, 3; –] [−2, −2, 3, 5, 3, −3; –]
5	3	32	2	[2, 2, −2, −2, 6, 6] ²
4	3	8	2	[−3, 2, −3, −2, 2, 2; –]
4	3	8	2	[−2, −2, 5, 2, 5, −2; –]
4	3	8	2	[6, −2, 2, 2, −2, −2, 6, 2, 2, −2, −2, 2]
4	3	48	2	[−2, −2, 2, 2] ³
4	3	4	3	[2, 3, −2, 3, −3, 3; –] [−4, 6, 4, 2, 6, −2] ²
4	3	4	3	[−4, 6, 3, 3, 6, −3, −3, 6, 4, 2, 6, −2] [−2, 3, −3, 4, −3, 3, 3, −4, −3, −3, 2, 3]
4	3	1	3	[−5, 2, −3, −2, 6, 4, 2, 5, −2, −4, 6, 3] [−2, 3, −3, 4, −3, 4, 2, −4, −2, −4, 2, 3] [3, −2, 3, −3, 5, −3, 2, 3, −2, −5, −3, 2]
3	3	4	3	[−5, −5, 4, 2, 6, −2, −4, 5, 5, 2, 6, −2] [4, −2, 3, 4, −4, −3, 3, −4, 2, −3, −2, 2]
3	3	8	3	[−5, −5, 3, 3, 6, −3, −3, 5, 5, 2, 6, −2] [2, 4, −2, 3, 5, −4, −3, 3, 3, −5, −3, −3]
4	3	2	3	[2, 4, −2, 3, 6, −4, −3, 2, 3, −2, 6, −3] [2, 4, −2, 3, 5, −4, −3, 4, 2, −5, −2, −4] [−5, 2, −3, −2, 5, 5, 2, 5, −2, −5, −5, 3]
4	3	2	3	[−5, 2, −3, −2, 6, 3, 3, 5, −3, −3, 6, 3] [4, −2, −4, 4, −4, 3, 3, −4, −3, −3, 4, 2] [−3, 3, 3, 4, −3, −3, 5, −4, 2, 3, −2, −5]
4	3	2	3	[2, 3, −2, 4, −3, 6, 3, −4, 2, −3, −2, 6] [−4, 5, −4, 2, 3, −2, −5, −3, 4, 2, 4, −2]
4	3	1	3	[6, 3, −4, −4, −3, 3, 6, 2, −3, −2, 4, 4] [−5, −4, 4, 2, 6, −2, −4, 5, 3, 4, 6, −3] [3, 4, 4, −3, 4, −4, −4, 3, −4, 2, −3, −2] [4, 5, −4, −4, −4, 3, −5, 2, −3, −2, 4, 4] [4, 5, −3, −5, −4, 3, −5, 2, −3, −2, 5, 3]
3	4	4	3	[4, 6, −4, −4, −4, 3, 3, 6, −3, −3, 4, 4] [−5, −4, 3, 3, 6, −3, −3, 5, 3, 4, 6, −3] [4, −3, 5, −4, −4, 3, 3, −5, −3, −3, 3, 4]
3	4	16	3	[3, 3, 4, −3, −3, 4; –] [3, 6, −3, −3, 6, 3] ²
4	3	1	3	[4, −2, 5, 2, −4, −2, 3, −5, 2, −3, −2, 2] [5, −2, 2, 4, −2, −5, 3, −4, 2, −3, −2, 2] [2, −5, −2, −4, 2, 5, −2, 2, 5, −2, −5, 4]	Фруктовый график
4	3	4	3	[−2, 6, 2, −4, −2, 3, 3, 6, −3, −3, 2, 4] [−2, 2, 5, −2, −5, 3, 3, −5, −3, −3, 2, 5]
4	3	2	3	[2, 4, −2, 6, 2, −4, −2, 4, 2, 6, −2, −4] [2, 5, −2, 2, 6, −2, −5, 2, 3, −2, 6, −3]
4	3	2	3	[6, 3, −3, −5, −3, 3, 6, 2, −3, −2, 5, 3] [3, 5, 3, −3, 4, −3, −5, 3, −4, 2, −3, −2] [−5, −3, 4, 2, 5, −2, −4, 5, 3, −5, 3, −3]
4	4	12	3	[3, −3, 5, −3, −5, 3, 3, −5, −3, −3, 3, 5]
4	3	2	3	[4, 2, 4, −2, −4, 4; –] [3, 5, 2, −3, −2, 5; –] [6, 2, −3, −2, 6, 3] ²
4	3	2	3	[3, 6, 4, −3, 6, 3, −4, 6, −3, 2, 6, −2] [4, −4, 5, 3, −4, 6, −3, −5, 2, 4, −2, 6] [−5, 5, 3, −5, 4, −3, −5, 5, −4, 2, 5, −2]
3	3	1	3	[6, −5, 2, 6, −2, 6, 6, 3, 5, 6, −3, 6] [6, 2, −5, −2, 4, 6, 6, 3, −4, 5, −3, 6] [5, 5, 6, 4, 6, −5, −5, −4, 6, 2, 6, −2] [−4, 4, −3, 3, 6, −4, −3, 2, 4, −2, 6, 3] [6, 2, −4, −2, 4, 4, 6, 4, −4, −4, 4, −4] [−3, 2, 5, −2, −5, 3, 4, −5, −3, 3, −4, 5] [−5, 2, −4, −2, 4, 4, 5, 5, −4, −4, 4, −5]
3	3	2	3	[2, 6, −2, 5, 6, 4, 5, 6, −5, −4, 6, −5] [5, 6, −4, −4, 5, −5, 2, 6, −2, −5, 4, 4] [2, 4, −2, −5, 4, −4, 3, 4, −4, −3, 5, −4] [2, −5, −2, 4, −5, 4, 4, −4, 5, −4, −4, 5]
4	3	4	3	[2, 4, −2, −5, 5] ² [−5, 2, 4, −2, 6, 3, −4, 5, −3, 2, 6, −2]
4	3	2	3	[−4, −4, 4, 2, 6, −2, −4, 4, 4, 4, 6, −4] [−4, −3, 4, 2, 5, −2, −4, 4, 4, −5, 3, −4] [−3, 5, 3, 4, −5, −3, −5, −4, 2, 3, −2, 5]
3	3	2	3	[2, 5, −2, 4, 4, 5; –] [2, 4, −2, 4, 4, −4; –] [−5, 5, 6, 2, 6, −2] ² [5, −2, 4, 6, 3, −5, −4, −3, 2, 6, −2, 2]
3	3	2	3	[3, 6, −4, −3, 5, 6, 2, 6, −2, −5, 4, 6] [2, −5, −2, 4, 5, 6, 4, −4, 5, −5, −4, 6] [5, −4, 4, −4, 3, −5, −4, −3, 2, 4, −2, 4]
4	3	2	3	[6, −5, 2, 4, −2, 5, 6, −4, 5, 2, −5, −2] [−2, 4, 5, 6, −5, −4, 2, −5, −2, 6, 2, 5] [5, −2, 4, −5, 4, −5, −4, 2, −4, −2, 5, 2]
4	3	1	3	[2, −5, −2, 6, 3, 6, 4, −3, 5, 6, −4, 6] [6, 3, −3, 4, −3, 4, 6, −4, 2, −4, −2, 3] [5, −4, 6, −4, 2, −5, −2, 3, 6, 4, −3, 4] [5, −3, 5, 6, 2, −5, −2, −5, 3, 6, 3, −3] [−5, 2, −5, −2, 6, 3, 5, 5, −3, 5, 6, −5] [−3, 4, 5, −5, −5, −4, 2, −5, −2, 3, 5, 5] [5, 5, 5, −5, 4, −5, −5, −5, −4, 2, 5, −2]
3	3	2	3	[5, −3, 6, 3, −5, −5, −3, 2, 6, −2, 3, 5] [2, 6, −2, −5, 5, 3, 5, 6, −3, −5, 5, −5] [5, 5, 5, 6, −5, −5, −5, −5, 2, 6, −2, 5] [4, −3, 5, 2, −4, −2, 3, −5, 3, −3, 3, −3] [5, 5, −3, −5, 4, −5, −5, 2, −4, −2, 5, 3]
4	3	4	3	[2, 4, −2, 5, 3, −4; –] [5, −3, 2, 5, −2, −5; –] [3, 6, 3, −3, 6, −3, 2, 6, −2, 2, 6, −2]
4	3	2	3	[6, 2, −4, −2, −5, 3, 6, 2, −3, −2, 4, 5] [2, 3, −2, 4, −3, 4, 5, −4, 2, −4, −2, −5] [−5, 2, −4, −2, −5, 4, 2, 5, −2, −4, 4, 5]
3	3	2	3	[5, 2, 5, −2, 5, −5; –] [6, 2, −4, −2, 4, 6] ² [2, −5, −2, 6, 2, 6, −2, 3, 5, 6, −3, 6] [−5, −2, 6, 6, 2, 5, −2, 5, 6, 6, −5, 2]
3	3	12	3	[−5, 3, 3, 5, −3, −3, 4, 5, −5, 2, −4, −2]
3	3	2	3	[6, −4, 3, 4, −5, −3, 6, −4, 2, 4, −2, 5] [−4, 6, −4, 2, 5, −2, 5, 6, 4, −5, 4, −5] [5, −5, 4, −5, 3, −5, −4, −3, 5, 2, 5, −2]
4	3	12	3	[−4, 5, 2, −4, −2, 5; –]	График Дюрера
3	3	4	3	[2, 5, −2, 5, 3, 5; –] [6, −2, 6, 6, 6, 2] ² [5, −2, 6, 6, 2, −5, −2, 3, 6, 6, −3, 2]
3	3	4	3	[6, −2, 6, 4, 6, 4, 6, −4, 6, −4, 6, 2] [5, 6, −3, 3, 5, −5, −3, 6, 2, −5, −2, 3]
3	3	4	3	[4, −2, 4, 6, −4, 2, −4, −2, 2, 6, −2, 2] [5, −2, 5, 6, 2, −5, −2, −5, 2, 6, −2, 2]
3	3	24	3	[6, −2, 2] ⁴	Усеченный тетраэдр
3	3	12	3		График Титце
3	3	36	3	[2, 6, −2, 6] ³
4	4	24	4	[−3, 3] ⁶ [3, −5, 5, −3, −5, 5] ²	Г _{6, 2} , Ю ₆	Юцис 18j-маркировка с символом: B
3	4	4	4	[6, −3, 6, 6, 3, 6] ² [6, 6, −5, 5, 6, 6] ² [3, −3, 4, −3, 3, 4; –] [5, −3, 6, 6, 3, −5] ² [5, −3, −5, 4, 4, −5; –] [6, 6, −3, −5, 4, 4, 6, 6, −4, −4, 5, 3]		Юцис 18j-маркировка с символом: L
3	4	8	4	[−4, 4, 4, 6, 6, −4] ² [6, −5, 5, −5, 5, 6] ² [4, −3, 3, 5, −4, −3; –] [−4, −4, 4, 4, −5, 5] ²		Юцис 18j-маркировка с символом: K
3	4	2	4	[−4, 6, 3, 6, 6, −3, 5, 6, 4, 6, 6, −5] [−5, 4, 6, 6, 6, −4, 5, 5, 6, 6, 6, −5] [5, −3, 4, 6, 3, −5, −4, −3, 3, 6, 3, −3] [4, −4, 6, 4, −4, 5, 5, −4, 6, 4, −5, −5] [4, −5, −3, 4, −4, 5, 3, −4, 5, −3, −5, 3]		Юцис 18j-маркировка с символом: T
3	4	2	4	[3, 4, 5, −3, 5, −4; –] [3, 6, −4, −3, 4, 6] ² [−4, 5, 5, −4, 5, 5; –] [3, 6, −4, −3, 4, 4, 5, 6, −4, −4, 4, −5] [4, −5, 5, 6, −4, 5, 5, −5, 5, 6, −5, −5] [4, −4, 5, −4, −4, 3, 4, −5, −3, 4, −4, 4]		Юцис 18j-маркировка с символом: R
3	4	8	4	[4, −4, 6] ⁴ [3, 6, 3, −3, 6, −3] ² [−3, 6, 4, −4, 6, 3, −4, 6, −3, 3, 6, 4]	Куб Бидиакиса	Юцис 18j-метка с символом: D
3	4	16	4	[6, −5, 5] ⁴ [3, 4, −4, −3, 4, −4] ²		Юцис 18j-маркировка с символом: G
3	4	2	4	[−3, 5, −3, 4, 4, 5; –] [4, −5, 5, 6, −4, 6] ² [−3, 4, −3, 4, 4, −4; –] [5, 6, −3, −5, 4, −5, 3, 6, −4, −3, 5, 3] [5, 6, 4, −5, 5, −5, −4, 6, 3, −5, 5, −3]		Юцис 18j-маркировка с символом: S
3	4	4	4	[4, −3, 4, 5, −4, 4; –] [4, 5, −5, 5, −4, 5; –] [−5, −3, 4, 5, −5, 4; –]		Юцис 18j-метка с символом: N
3	4	2	4	[6, −4, 6, −4, 3, 5, 6, −3, 6, 4, −5, 4] [6, −4, 3, −4, 4, −3, 6, 3, −4, 4, −3, 4] [5, 6, −4, 3, 5, −5, −3, 6, 3, −5, 4, −3] [5, −5, 4, 6, −5, −5, −4, 3, 5, 6, −3, 5] [5, 5, −4, 4, 5, −5, −5, −4, 3, −5, 4, −3]		Yutsis 18j-symbol label: V
3	4	4	4	[6, −3, 5, 6, −5, 3, 6, −5, −3, 6, 3, 5] [3, −4, 5, −3, 4, 6, 4, −5, −4, 4, −4, 6]		Юцис 18j-маркировка с символом: P
3	4	8	4	[5, 6, 6, −4, 5, −5, 4, 6, 6, −5, −4, 4]		Юцис 18j-символ метки: I
3	5	16	4	[4, −5, 4, −5, −4, 4; –]		Юцис 18j-маркировка с символом: F
3	4	4	4	[6, 4, 6, 6, 6, −4] ² [−3, 4, −3, 5, 3, −4; –] [−5, 3, 6, 6, −3, 5, 5, 5, 6, 6, −5, −5] [−3, 3, 6, 4, −3, 5, 5, −4, 6, 3, −5, −5]		Юцис 18j-маркировка с символом: M
4	4	8	4	[3, 5, 5, −3, 5, 5; –] [−3, 5, −3, 5, 3, 5; –] [5, −3, 5, 5, 5, −5; –]		Юцис 18j-маркировка с символом: E
3	4	48	4	[5, −5, −3, 3] ³ [−5, 5] ⁶	Граф Франклина	Юцис 18j-маркировка с символом: C
3	4	24	4	[6] ¹² [6, 6, −3, −5, 5, 3] ²		Юцис 18j-маркировка с символом: A
3	5	18	4	[6, −5, −4, 4, −5, 4, 6, −4, 5, −4, 4, 5]		Юцис 18j-маркировка с символом: H

Записи LCF отсутствуют выше, если граф не имеет гамильтонова цикла , что встречается редко (см. гипотезу Тейта ). В этом случае идентификатором служит список ребер между парами вершин, помеченных от 0 до n−1 в третьем столбце.

Векторные коэффициенты связи

Каждый 4-связный (в указанном выше смысле) простой кубический граф на $2 n$ вершинах определяет класс квантовомеханических $3 n$ -j символов. Грубо говоря, каждая вершина представляет собой 3-jm-символ , граф преобразуется в орграф путем присвоения знаков квантовым числам углового момента $j$ , вершины помечаются стрелками, представляющими порядок трех $j$ (трех ребер) в символе 3-jm, а граф представляет собой сумму произведения всех этих чисел, присвоенных вершинам.

Есть 1 ( 6-j ), 1 ( 9-j ), 2 (12-j), 5 (15-j), 18 (18-j), 84 (21-j), 607 (24-j). , 6100 (27-j), 78824 (30-j), 1195280 (33-j), 20297600 (36-j), 376940415 (39-j) и т. д. из них (последовательность A175847 в OEIS ).

Если они эквивалентны определенным двоичным деревьям, индуцированным вершинами (разрезание одного ребра и поиск разреза, который разбивает оставшийся граф на два дерева), они являются представлениями коэффициентов связи и тогда также известны как графы Юциса (последовательность A111916 в OEIS ).

См. также

Ссылки

Юцис, АП ; Левинсон, IB; Ванагас, В.В.; Сен, А. (1962). Математический аппарат теории углового момента . Израильская программа научных переводов. Бибкод : 1962mata.book.....Y .
Массо, Ж.-Н.; Эль-Баз, Э.; Лафукер, Ж. (1967). «Общий графический метод определения углового момента». Обзоры современной физики . 39 (2): 288–305. Бибкод : 1967RvMp...39..288M . дои : 10.1103/RevModPhys.39.288 .
Буссемейкер, ФК; Кобельич, С.; Цветкович, ДМ (1976). «Компьютерные исследования кубических графов» (PDF) .
Буссемейкер, ФК; Кобельич, С.; Цветкович, Д.М.; Зайдель, Джей-Джей (1977). «Кубические графы с <=14 вершинами» . Дж. Комбин. Теория Сер. Б. 23 (2–3): 234–235. дои : 10.1016/0095-8956(77)90034-X .
Фрухт, Р. (1977). «Каноническое представление трехвалентных гамильтоновых графов». Журнал теории графов . 1 (1): 45–60. дои : 10.1002/jgt.3190010111 . МР 0463029 .
Кларк, Л.; Энтрингер, Р. (1983). «Наименьшие максимально негамильтоновы графы». Пер. Матем. Венгрия . 14 (1): 57–68. дои : 10.1007/BF02023582 . МР 0697357 . S2CID 122218690 .
Вормальд, Северная Каролина (1985). «Перечисление циклически 4-связных кубических графов». Журнал теории графов . 9 (4): 563–573. дои : 10.1002/jgt.3190090418 . МР 0890248 .
Бар-Шалом, А.; Клапиш, М. (1988). «NJGRAF - эффективная программа для расчета общих коэффициентов связи путем графического анализа, совместимая с NJSYM». Вычислить. Физ. Коммун . 50 (3): 375–393. Бибкод : 1988CoPhC..50..375B . дои : 10.1016/0010-4655(88)90192-0 .
Бринкманн, Г. (1996). «Быстрая генерация кубических графов». Журнал теории графов . 23 (2): 139–149. doi : 10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.0.CO;2-U . МР 1408342 .
Фак, В.; Питре, С.Н.; Ван дер Югт, Дж. (1997). «Расчет общих коэффициентов компенсации графическими методами». Вычислить. Физ. Коммун . 101 (1–2): 155–170. Бибкод : 1997CoPhC.101..155F . дои : 10.1016/S0010-4655(96)00170-1 .
Данос, М.; Фано, У. (1998). «Графический анализ углового момента продуктов столкновения». Отчеты по физике . 304 (4): 155–227. Бибкод : 1998PhR...304..155D . дои : 10.1016/S0370-1573(98)00020-9 .
Мерингер, М. (1999). «Быстрое построение регулярных графов и построение клеток». Журнал теории графов . 30 (2): 137–146. doi : 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G . МР 1665972 .
Ван Дейк, Д.; Бринкманн, Г.; Фак, В.; Маккей, Б.Д. (2005). «Быть или не быть Юцису: Алгоритмы решения проблемы». Вычислить. Физ. Коммун . 173 (1–2): 61–70. Бибкод : 2005CoPhC.173...61В . дои : 10.1016/j.cpc.2005.07.008 . МР 2179511 .
Ван Дейк, Д.; Фак, В. (2007). «О редукции графов Юциса» . Дискретная математика . 307 (11–12): 1506–1515. дои : 10.1016/j.disc.2005.11.088 . МР 2311125 .
Олдред, REL; Ван Дейк, Д.; Бринкманн, Г.; Фак, В.; Маккей, Б.Д. (2009). «Структурные свойства графов, не принадлежащих Юцису, обеспечивающие быстрое распознавание». Дискретная математика . 157 (2): 377–386. дои : 10.1016/j.dam.2008.03.020 . HDL : 1942/9184 . МР 2479811 .
Матар, Ричард Дж. (2011). «Графы Вигнера до 12 вершин». arXiv : 1109.2358 [ math-ph ].