В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами.
Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.
Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.
В теории графов снарк Уоткинса — снарк с 50 вершинами и 75 рёбрами. Открыт Джоном Д. Уоткинсом в 1989 году.
Снарк Блануши — 3-регулярный граф с 18 вершинами и 27 рёбрами. Существуют два таких графа. Носят имя нашедшего оба этих графа в 1946 году югославского математика Данило Блануши.
В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.
Граф Дика — 3-регулярный граф с 32 вершинами и 48 рёбрами, назван в честь Вальтера фон Дика .
Граф Фостера — двудольный 3-регулярный граф с 90 вершинами и 135 рёбрами. Граф Фостера является гамильтоновым, имеет хроматическое число 2, хроматический индекс 3, радиус 8, диаметр 8 и обхват 10. Также является вершинно 3-связным и рёберно 3-связным.
Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году.
Граф Биггса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами. Назван в честь Биггса и Смита, описавших граф в 1971 году.
Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
В теории графов граф Титце — это неориентированный кубический граф с 12 вершинами и 18 рёбрами. Граф назван именем Генриха Титце, показавшего в 1910 году, что ленту Мёбиуса можно разделить на шесть областей, касающихся друг друга — три вдоль границы ленты и три вдоль центральной линии — а потому для графов, допускающих вложение в ленту Мёбиуса, может потребоваться шесть цветов. Граничные сегменты областей Титца разделения ленты Мёбиуса образуют вложение графа Титце.
В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.
Двойное покрытие циклами в теории графов — множество циклов в неориентированном графе, которое включает в себя каждое ребро ровно два раза. Например, любой полиэдральный граф образован из вершин и рёбер выпуклого многогранника, грани же при этом образуют двойное покрытие циклами: каждое ребро принадлежит ровно двум граням.
В теории графов граф «бабочка» — это планарный неориентированный граф с 5 вершинами и 6 рёбрами. Граф может быть построен объединением двух копий циклов C3 по одной общей вершине, а потому граф изоморфен графу дружеских отношений F2.
11-клетка Балабана или (3-11)-клетка Балабана — это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана.
Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным. Такие графы не часто встречаются. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976 и 1981 соответственно.
Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман и опубликовал в 1963. Граф коспектрален графу гиперкуба Q4.
Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона.
Бидиакис-куб — это 3-регулярный граф с 12 вершинами и 18 рёбрами.
Медиафайлы на Викискладе
Хроматическое число двойной звезды равно 3.
Хроматический индекс двойной звезды равен 4.