Квартикальный граф

Граф со всеми вершинами степени 4

В математической области теории графов квартикальный граф — это граф , в котором все вершины имеют степень 4. Другими словами, квартикальный граф — это 4- регулярный граф . ^[1]

Примеры

Несколько известных графов являются квартикальными. Они включают в себя:

Полный граф K ₅ , граф четвертой степени с 5 вершинами, наименьший возможный граф четвертой степени.
Граф Хватала , еще один граф четвертой степени с 12 вершинами, наименьший граф четвертой степени, который не только не имеет треугольников, но и не может быть раскрашен тремя цветами. ^[2]
Граф Фолкмана , квартикальный граф с 20 вершинами, наименьший полусимметричный граф . ^[3]
Граф Мередита , граф четвертой степени с 70 вершинами, который является 4-связным , но не имеет гамильтонова цикла , опровергающий гипотезу Криспина Нэша-Вильямса . ^[4]

Каждый медиальный граф является графом квартикальной плоскости , а каждый граф квартикальной плоскости является медиальным графом пары дуальных графов или мультиграфов. ^[5] Диаграммы узлов и диаграммы связей также являются мультиграфами квартикальной плоскости , в которых вершины представляют собой пересечения диаграммы и помечены дополнительной информацией о том, какая из двух ветвей узла пересекает другую ветвь в этой точке. ^[6]

Характеристики

Поскольку степень каждой вершины в графе квартики четная, каждый связный граф квартики имеет эйлеров цикл . И как и в случае с регулярными двудольными графами в более общем смысле, каждый двудольный граф квартики имеет идеальное паросочетание . В этом случае возможен гораздо более простой и быстрый алгоритм для нахождения такого паросочетания, чем для нерегулярных графов: выбирая каждое второе ребро эйлерова цикла, можно найти 2-фактор , который в этом случае должен быть набором циклов, каждый из которых имеет четную длину, причем каждая вершина графа появляется ровно в одном цикле. Выбирая каждое второе ребро снова в этих циклах, можно получить идеальное паросочетание за линейное время . Тот же метод можно использовать для раскраски ребер графа четырьмя цветами за линейное время. ^[7]

Квартикальные графы имеют четное число гамильтоновых разложений . ^[8]

Открытые проблемы

Открытая гипотеза, имеют ли все квартикальные гамильтоновы графы четное число гамильтоновых контуров или имеют более одного гамильтонова контура. Известно, что ответ неверен для квартикальных мультиграфов . ^[9]

Смотрите также

Кубический граф

Ссылки

^ Toida, S. (1974), «Построение графов четвертой степени», Журнал комбинаторной теории , Серия B, 16 : 124–133 , doi : 10.1016/0095-8956(74)90054-9 , MR 0347693.
^ Chvátal, V. (1970), «Наименьший 4-хроматический 4-регулярный граф без треугольников», Журнал комбинаторной теории , 9 (1): 93–94 , doi : 10.1016/S0021-9800(70)80057-6.
^ Фолкман, Джон (1967), «Регулярные линейно-симметричные графы», Журнал комбинаторной теории , 3 : 215–232 , doi : 10.1016/s0021-9800(67)80069-3 , MR 0224498.
^ Мередит, GHJ (1973), «Регулярные n -валентные n -связные негамильтоновы не- n- рёберно-раскрашиваемые графы», Журнал комбинаторной теории , Серия B, 14 : 55–60 , doi : 10.1016/s0095-8956(73)80006-1 , MR 0311503.
^ Бонди, Дж.А.; Хэггквист, Р. (1981), «Непересекающиеся по краям циклы Гамильтона в 4-регулярных плоских графах», Aequationes Mathematicae , 22 (1): 42–45 , doi : 10.1007/BF02190157, MR 0623315 .
^ Welsh, Dominic JA (1993), «Сложность узлов», Quo vadis, теория графов?, Annals of Discrete Mathematics, т. 55, Амстердам: Северная Голландия, стр. 159–171 , doi :10.1016/S0167-5060(08)70385-6, MR 1217989 .
^ Габов, Гарольд Н. (1976), «Использование разбиений Эйлера для раскраски двудольных мультиграфов», Международный журнал компьютерных и информационных наук , 5 (4): 345–355 , doi :10.1007/bf00998632, MR 0422081 .
^ Томасон, АГ (1978), «Гамильтоновы циклы и графы, раскрашиваемые уникальным образом», Анналы дискретной математики , 3 : 259–268 , doi :10.1016/s0167-5060(08)70511-9, MR 0499124 .
^ Флейшнер, Герберт (1994), «Уникальность максимальных доминирующих циклов в 3-регулярных графах и гамильтоновых циклов в 4-регулярных графах», Журнал теории графов , 18 (5): 449– 459, doi :10.1002/jgt.3190180503, MR 1283310 .

Внешние ссылки

Вайсштейн, Эрик В. «Граф четвертой степени». MathWorld .

[1] Toida, S. (1974), «Построение графов четвертой степени», Журнал комбинаторной теории , Серия B, 16 : 124–133 , doi : 10.1016/0095-8956(74)90054-9 , MR 0347693.

[2] Chvátal, V. (1970), «Наименьший 4-хроматический 4-регулярный граф без треугольников», Журнал комбинаторной теории , 9 (1): 93–94 , doi : 10.1016/S0021-9800(70)80057-6.

[3] Фолкман, Джон (1967), «Регулярные линейно-симметричные графы», Журнал комбинаторной теории , 3 : 215–232 , doi : 10.1016/s0021-9800(67)80069-3 , MR 0224498.

[4] Мередит, GHJ (1973), «Регулярные n -валентные n -связные негамильтоновы не- n- рёберно-раскрашиваемые графы», Журнал комбинаторной теории , Серия B, 14 : 55–60 , doi : 10.1016/s0095-8956(73)80006-1 , MR 0311503.

[5] Бонди, Дж.А.; Хэггквист, Р. (1981), «Непересекающиеся по краям циклы Гамильтона в 4-регулярных плоских графах», Aequationes Mathematicae , 22 (1): 42–45 , doi : 10.1007/BF02190157, MR 0623315 .

[6] Welsh, Dominic JA (1993), «Сложность узлов», Quo vadis, теория графов?, Annals of Discrete Mathematics, т. 55, Амстердам: Северная Голландия, стр. 159–171 , doi :10.1016/S0167-5060(08)70385-6, MR 1217989 .

[7] Габов, Гарольд Н. (1976), «Использование разбиений Эйлера для раскраски двудольных мультиграфов», Международный журнал компьютерных и информационных наук , 5 (4): 345–355 , doi :10.1007/bf00998632, MR 0422081 .

[8] Томасон, АГ (1978), «Гамильтоновы циклы и графы, раскрашиваемые уникальным образом», Анналы дискретной математики , 3 : 259–268 , doi :10.1016/s0167-5060(08)70511-9, MR 0499124 .

[9] Флейшнер, Герберт (1994), «Уникальность максимальных доминирующих циклов в 3-регулярных графах и гамильтоновых циклов в 4-регулярных графах», Журнал теории графов , 18 (5): 449– 459, doi :10.1002/jgt.3190180503, MR 1283310 .