Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба 5-го порядка. Назван графом Клебша в 1968 году Зайделем ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем. 40-рёберный вариант – это складной граф куба 5 порядка. Он известен также под именем граф Гринвуда — Глизона после работы Гринвуда и Глизона, в которой они использовали этот граф для вычисления числа Рамсея R (3,3,3) = 17 .
Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика Герберта Грёча и он демонстрирует необходимость предположения планарности в теореме Грёча, которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с нуль-графа. Эта последовательность графов была использована Мыцельским, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом.
Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда.
В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа. Он назван в честь Паппа Александрийского, математика Древней Греции, который верил, что доказал «теорему о шестиугольнике», в которой описывал конфигурацию Паппа. Все кубические дистанционно-регулярные графы известны. Граф Паппа — один из тринадцати таких графов.
Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.
Граф Биггса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами. Назван в честь Биггса и Смита, описавших граф в 1971 году.
Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.
Граф Вагнера — 3-регулярный граф с 8 вершинами и 12 рёбрами, является 8-вершинной лестницей Мёбиуса.
Граф Хватала — неориентированный граф с 12 вершинами и 24 рёбрами, открытый Вацлавом Хваталом в 1970 году.
Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе.
Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления. Плоское вложение — вложение, при котором любой цикл является границей топологического круга, внутренность которого не зацеплена с графом. Вложимый без зацеплений граф — граф, имеющий незацепленное или плоское вложение. Эти графы образуют трёхмерный аналог планарным графам. В противоположность, существенно зацепленный граф — это граф, не имеющий незацепленного вложения.
В теории графов псевдолес — это неориентированный граф, в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
В теории графов «кактус» — это связный граф, в котором любые два простых цикла имеют не более одной общей вершины. Эквивалентно, любое ребро в таком графе принадлежит максимум одному простому циклу. Эквивалентно, любой блок является ребром или циклом.
В теории графов граф «бабочка» — это планарный неориентированный граф с 5 вершинами и 6 рёбрами. Граф может быть построен объединением двух копий циклов C3 по одной общей вершине, а потому граф изоморфен графу дружеских отношений F2.
Граф F26A — симметричный двудольный кубический граф с 26 вершинами и 39 рёбрами.
Граф Аполлония — неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.
Голова быка — планарный неориентированный граф с 5 вершинами и 5 рёбрами в форме треугольника с двумя непересекающимися висячими рёбрами.
110-вершинный граф Иванова — Иофиновой — полусимметричный кубический граф с 110 вершинами и 165 рёбрами.
Медиафайлы на Викискладе
