В математической области теории графов граф -бабочка (также называемый графом-бабочкой и графом-песочными часами ) представляет собой плоский неориентированный граф с 5 вершинами и 6 ребрами. [1] [2] Его можно построить, соединив 2 копии графа -цикла C 3 с общей вершиной, и поэтому он изоморфен графу дружбы F 2 .
Граф-бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым , так и пенни-графом (это подразумевает, что он единичного расстояния и планарен ). Он также является 1- вершинно-связным графом и 2- рёберно-связным графом .
Существует всего три неграциозных простых графа с пятью вершинами. Один из них — граф-бабочка. Два других — граф-цикл C 5 и полный граф K 5 . [3]
Граф является графом без галстуков-бабочек , если он не имеет бабочки в качестве индуцированного подграфа . Графы без треугольников являются графами без галстуков-бабочек, поскольку каждая бабочка содержит треугольник.
В графе с k -вершинной связностью ребро называется k -стягиваемым, если стягивание ребра приводит к k -связному графу. Андо, Канеко, Каварабаяши и Ёсимото доказали, что любой граф без галстуков-бабочек с k -вершинной связностью имеет k -стягиваемое ребро. [4]
Полная группа автоморфизмов графа бабочки — это группа порядка 8, изоморфная диэдральной группе D4 , группе симметрий квадрата , включающей как вращения, так и отражения.
Характеристический многочлен графа бабочки равен .
