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

Граф Хватала

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

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

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

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

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

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

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

• 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.