Граф бабочки

Граф бабочки
Граф бабочки
Вершины	5
Края	6
Радиус	1
Диаметр	2
Обхват	3
Автоморфизмы	8 ( Д 4 )
Хроматическое число	3
Хроматический индекс	4
Характеристики	Планарный ; Единичное расстояние ; Эйлеров ; Не изящный
	Таблица графиков и параметров

В математической области теории графов граф -бабочка (также называемый графом-бабочкой и графом песочных часов ) представляет собой плоский неориентированный граф с 5 вершинами и 6 ребрами. ^[1]^[2] Он может быть построен путем соединения двух копий графа циклов $C 3$ с общей вершиной и, следовательно, изоморфен графу дружбы $F 2$ .

Граф-бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является одновременно эйлеровым и пенни-графом (это означает, что он имеет единичное расстояние и является плоским ). Это также 1 -связный граф и 2 -связный граф .

Существует только три неизящных простых графа с пятью вершинами. Одним из них является граф-бабочка. Два других — это граф циклов $C 5$ и полный граф $K 5$ . ^[3]

Графики без галстуков-бабочек

Граф является свободным от галстука-бабочки , если он не имеет бабочки в качестве индуцированного подграфа . Графы без треугольников — это графы без галстуков-бабочек, поскольку каждая бабочка содержит треугольник.

В k -связном графе ребро называется k -связным, если в результате сжатия ребра образуется k -связный граф. Андо, Канеко, Каварабаяши и Ёсимото доказали, что каждый k граф без галстука-бабочки, связный с -вершинами, имеет k -стягиваемое ребро. ^[4]

Алгебраические свойства

Полная группа автоморфизмов графа-бабочки — это группа порядка 8, изоморфная группе диэдра D ₄ , группе симметрий квадрата , включающей как вращения, так и отражения.

Характеристический полином графа-бабочки равен $-(x-1)(x+1)^{2}(x^{2}-x-4)$ .

Ссылки

^ Вайсштейн, Эрик В. «Граф бабочки» . Математический мир .
^ ISGCI: Информационная система по классам графов и их включениям. « Список малых графов ».
^ Вайсштейн, Эрик В. «Изящный график» . Математический мир .
^ Андо, Киёси (2007), «Сжимаемые ребра в k -связном графе», Дискретная геометрия, комбинаторика и теория графов , Конспекты лекций по вычислительной технике. наук, том. 4381, Springer, Berlin, стр. 10–20, номер документа : 10.1007/978-3-540-70666-3_2 , MR 2364744 .

[1] Вайсштейн, Эрик В. «Граф бабочки» . Математический мир .

[2] ISGCI: Информационная система по классам графов и их включениям. « Список малых графов ».

[Mat2007-3] Вайсштейн, Эрик В. «Изящный график» . Математический мир .

[4] Андо, Киёси (2007), «Сжимаемые ребра в k -связном графе», Дискретная геометрия, комбинаторика и теория графов , Конспекты лекций по вычислительной технике. наук, том. 4381, Springer, Berlin, стр. 10–20, номер документа : 10.1007/978-3-540-70666-3_2 , MR 2364744 .

[1]

[2]

[3]

[4]