Квадратичный граф

Квадратичный граф — граф, в котором все вершины имеют степень 4. Другими словами, квадратичный граф является 4-регулярным графом.

Примеры

Граф Хватала

Некоторые хорошо известные графы являются квадратичными. Это такие графы, как:

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

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

Свойства

Поскольку степень любой вершины в квадратичном графе чётна, любой связный квадратичный граф имеет эйлеров цикл. Как и для регулярных двудольных графов, любой двудольный квадратичный граф имеет совершенное паросочетание. В этом случае возможен много более простой и быстрый алгоритм поиска паросочетания, чем для нерегулярных графов — при выборе любого другого ребра эйлерова цикла можем получить 2-фактор, который, в данном случае, должен быть коллекцией циклов, каждый из которых имеет чётную длину, а каждая вершина графа появляется ровно в одном цикле. При выборе любого другого ребра в этих циклах получаем совершенное паросочетание за линейное время. Тот же метод может быть использован для раскраски рёбра графа в четыре цвета за линейное время.

Квадратичные графы имеют чётное число гамильтоновых разложений.

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

Открытой проблемой является гипотеза, все ли квадратичные гамильтоновы графы имеют чётное число гамильтоновых циклов, или имеют более одного гамильтонова цикла. Известно, что для квадратичных мультиграфов ответ НЕТ.

См. также

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

Литература

• Toida S. Construction of quartic graphs // Journal of Combinatorial Theory. — 1974. — Т. 16. — С. 124–133. — doi:10.1016/0095-8956(74)90054-9.
• Chvátal V. The smallest triangle-free 4-chromatic 4-regular graph // Journal of Combinatorial Theory. — 1970. — Т. 9, вып. 1. — С. 93–94. — doi:10.1016/S0021-9800(70)80057-6.
• Jon Folkman. Regular line-symmetric graphs // Journal of Combinatorial Theory. — 1967. — Т. 3. — С. 215–232. — doi:10.1016/s0021-9800(67)80069-3.
• Meredith G. H. J. Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphs // Journal of Combinatorial Theory. — 1973. — Т. 14. — С. 55–60. — doi:10.1016/s0095-8956(73)80006-1.
• Bondy J. A., Häggkvist R. Edge-disjoint Hamilton cycles in 4-regular planar graphs // Aequationes Mathematicae. — 1981. — Т. 22, вып. 1. — С. 42–45. — doi:10.1007/BF02190157.
• Dominic J. A. Welsh. The complexity of knots // Quo vadis, graph theory?. — Amsterdam: North-Holland, 1993. — Т. 55. — С. 159–171. — (Annals of Discrete Mathematics). — doi:10.1016/S0167-5060(08)70385-6.
• Harold N. Gabow. Using Euler partitions to edge color bipartite multigraphs // International Journal of Computer and Information Sciences. — 1976. — Т. 5, вып. 4. — С. 345–355. — doi:10.1007/bf00998632.
• Thomason A. G. Hamiltonian cycles and uniquely edge colourable graphs // Annals of Discrete Mathematics. — 1978. — Т. 3. — С. 259–268. — doi:10.1016/s0167-5060(08)70511-9.
• Herbert Fleischner. Uniqueness of maximal dominating cycles in 3-regular graphs and of Hamiltonian cycles in 4-regular graphs // Journal of Graph Theory. — 1994. — Т. 18, вып. 5. — С. 449–459. — doi:10.1002/jgt.3190180503.

Ссылки

• Weisstein, Eric W. Quartic Graph (англ.) на сайте Wolfram MathWorld.