Метелик (теорія графів)

У теорії графів граф «метелик» (а також «краватка-метелик» або «пісковий годинник») — це планарний неорієнтований граф з 5 вершинами і 6 ребрами. Граф можна побудувати об'єднанням двох копій циклів C₃ за однією спільною вершиною, а тому граф ізоморфний графу товаришування F₂.

Метелик має діаметр 2 і обхват 3, радіус 1, хроматичне число 3, хроматичний індекс 4 і є як ейлеровим, так і графом одиничних відстаней. Граф є вершинно 1-зв'яним і реберно 2-зв'язним.

Існує тільки 3 простих графів з п'ятьма вершинами, що не мають граціозної розмітки. Один з них — метелик. Два інших — цикл C₅ і повний граф K₅.

Графи, що не містять метеликів

Граф є вільним від метеликів, якщо він не має метелика породженим підграфом. Графи без трикутників є графами без метеликів, оскільки граф-метелик містить трикутники.

У вершинно k-зв'язному графі ребро називають k-стягувальним, якщо стягування ребра призводить до k-зв'язного графу. Андо, Канеко, Каварабаяші і Йошімото довели, що будь-який вершинно k-зв'язний граф без метеликів має k-стягувальне ребро.

Алгебричні властивості

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

Характеристичним многочленом матриці графу-метелика є $-(x-1)(x+1)^{2}(x^{2}-x-4)$.

Література

• Kiyoshi Ando. Discrete geometry, combinatorics and graph theory. — Springer, Berlin, 2007. — Т. 4381. — С. 10–20. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/978-3-540-70666-3_2.