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

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

Примеры

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

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

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

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

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

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

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

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

См. также

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

Ссылки

^ Тойда, С. (1974), «Построение графов квартики», Журнал комбинаторной теории , серия B, 16 : 124–133, doi : 10.1016/0095-8956(74)90054-9 , MR 0347693 .
^ Хватал, В. (1970), «Наименьший 4-хроматический 4-правильный граф без треугольников», Journal of Combinatorial Theory , 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 - графы, не раскрашиваемые ребрам», Journal of Combinatorial Theory , Series B, 14 : 55–60, doi : 10.1016/s0095-8956(73) 80006-1 , МР 0311503 .
^ Бонди, Дж.А.; Хэггквист, Р. (1981), «Непересекающиеся по краям циклы Гамильтона в 4-регулярных плоских графах», Aequationes Mathematicae , 22 (1): 42–45, doi : 10.1007/BF02190157 , MR 0623315 .
^ Уэлш, Доминик Дж. А. (1993), «Сложность узлов», Quo vadis, теория графов? , Анналы дискретной математики, вып. 55, Амстердам: Северная Голландия, стр. 159–171, номер документа : 10.1016/S0167-5060(08)70385-6 , MR 1217989 .
^ Габоу, Гарольд Н. (1976), «Использование разбиений Эйлера для граничных цветных двудольных мультиграфов», Международный журнал компьютерных и информационных наук , 5 (4): 345–355, doi : 10.1007/bf00998632 , MR 0422081 .
^ Томасон, А.Г. (1978), «Гамильтоновы циклы и графы, раскрашиваемые однозначно по краям», Annals of Discrete Mathematics , 3 : 259–268, doi : 10.1016/s0167-5060(08)70511-9 , MR 0499124 .
^ Флейшнер, Герберт (1994), «Единственность максимальных доминирующих циклов в 3-регулярных графах и гамильтоновых циклов в 4-регулярных графах», Journal of Graph Theory , 18 (5): 449–459, doi : 10.1002/jgt.3190180503 , МР 1283310 .

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

Вайсштейн, Эрик В. «Квартичный граф» . Математический мир .

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

[2] Хватал, В. (1970), «Наименьший 4-хроматический 4-правильный граф без треугольников», Journal of Combinatorial Theory , 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 - графы, не раскрашиваемые ребрам», Journal of Combinatorial Theory , Series B, 14 : 55–60, doi : 10.1016/s0095-8956(73) 80006-1 , МР 0311503 .

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

[6] Уэлш, Доминик Дж. А. (1993), «Сложность узлов», Quo vadis, теория графов? , Анналы дискретной математики, вып. 55, Амстердам: Северная Голландия, стр. 159–171, номер документа : 10.1016/S0167-5060(08)70385-6 , MR 1217989 .

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]