График быка
| График быка | |
|---|---|
 Бычий график | |
| Вершины | 5 |
| Края | 5 |
| Радиус | 2 |
| Диаметр | 3 |
| Обхват | 3 |
| Автоморфизмы | 2 ( Z /2 Z ) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Характеристики | Расстояние в плоскости |
| Таблица графиков и параметров | |
В математической области теории графов бычий граф — это плоский неориентированный граф с 5 вершинами и 5 ребрами, в форме треугольника с двумя непересекающимися висячими ребрами. [1]
Он имеет хроматическое число 3, хроматический индекс 3, радиус 2, диаметр 3 и обхват 3. Он также является самодополнительным графом , блочным графом , разделенным графом , интервальным графом , графом без клешней , графом с 1 вершинной связностью и графом с 1 рёберной связностью .
Графики без быков
Граф является свободным от быков, если он не имеет быка в качестве индуцированного подграфа . Графы без треугольников являются свободными от быков, поскольку каждый бык содержит треугольник. Сильная теорема о совершенном графе была доказана для графов без быков задолго до ее доказательства для общих графов, [2] и известен алгоритм распознавания за полиномиальное время для совершенных графов без быков. [3]
Мария Чудновски и Шмуэль Сафра изучили графы без быков в более общем плане, показав, что любой такой граф должен иметь либо большую клику , либо большое независимое множество (то есть гипотеза Эрдёша–Хайнала верна для графа с быками) [4] и разработав общую теорию структуры для этих графов. [5] [6] [7]
Хроматический и характеристический многочлен
Хроматический многочлен бычьего графа равен . Два других графа хроматически эквивалентны бычьему графу.
Его характеристический многочлен равен .
Его полином Тутте равен .
Ссылки
- ^ Вайсштейн, Эрик В. «Bull Graph». MathWorld .
- ^ Chvátal, V. ; Sbihi, N. (1987), «Без быков графы Берже совершенны», Графы и комбинаторика , 3 (1): 127–139, doi :10.1007/BF01788536, S2CID 44570627.
- ^ Рид, Б.; Сбихи , Н. (1995), «Распознавание совершенных графов без быков», Графы и комбинаторика , 11 (2): 171–178, doi :10.1007/BF01929485, S2CID 206808701.
- ^ Чудновский, М .; Сафра, С. (2008), «Гипотеза Эрдёша–Хайнала для графов без быков», Журнал комбинаторной теории , Серия B, 98 (6): 1301–1310, CiteSeerX 10.1.1.606.3091 , doi : 10.1016/j.jctb.2008.02.005 .
- ^ Чудновский, М. (2008), Структура графов без быков. I. Трехреберные пути с центрами и антицентрами (PDF).
- ^ Чудновский, М. (2008), Структура графов без быков. II. Элементарные триграфы (PDF).
- ^ Чудновский, М. (2008), Структура графов без быков. III. Глобальная структура (PDF).
