Бычий график - Википедия - Bull graph

Бычий график
Бык graph.circo.svg
График быка
Вершины5
Края5
Радиус2
Диаметр3
Обхват3
Автоморфизмы2 (Z/2Z)
Хроматическое число3
Хроматический индекс3
ХарактеристикиПланарный
Единичное расстояние
Таблица графиков и параметров

в математический поле теория графов, то бычий график это планарный неориентированный граф с 5 вершинами и 5 ребрами, в виде треугольника с двумя непересекающимися висячими ребрами.[1]

Она имеет хроматическое число 3, хроматический индекс 3, радиус 2, диаметр 3 и обхват 3. Это также самодополняющий граф, а блочный граф, а разделенный график, интервальный график, а граф без когтей, а 1-вершинно-связный граф и 1-реберный граф.

Графы без быков

График не имеет быков, если в нем нет быков. индуцированный подграф. В графы без треугольников графы без быков, поскольку каждый бык содержит треугольник. В сильная теорема о совершенном графе было доказано для графов без быков задолго до его доказательства для общих графов,[2] и полиномиальное время Алгоритм распознавания идеальных графов без быков известен.[3]

Мария Чудновская и Шмуэль Сафра изучали графы без быков в более общем плане, показывая, что любой такой граф должен иметь либо большой клика или большой независимый набор (это Гипотеза Эрдеша – Хайнала для бычьего графа),[4] и разработка общей теории структуры этих графов.[5][6][7]

Хроматический и характеристический полином

Три графика с хроматический полином равно .

В хроматический полином графа быков . Два других графа хроматически эквивалентны графу быка.

Его характеристический многочлен является .

Его Полином Тутте является .

Рекомендации

  1. ^ Вайсштейн, Эрик В. «Бычий график». MathWorld.
  2. ^ Хватал, В.; Сбихи, Н. (1987), "Булл-свободные графы Берже идеальны", Графы и комбинаторика, 3 (1): 127–139, Дои:10.1007 / BF01788536.
  3. ^ Рид, Б.; Сбихи, Н. (1995), "Распознавание идеальных графов без быков", Графы и комбинаторика, 11 (2): 171–178, Дои:10.1007 / BF01929485.
  4. ^ Чудновский, М.; Сафра, С. (2008), "Гипотеза Эрдеша – Хайнала для графов без быков", Журнал комбинаторной теории, Серия B, 98 (6): 1301–1310, Дои:10.1016 / j.jctb.2008.02.005, заархивировано из оригинал на 2010-06-25, получено 2009-06-30.
  5. ^ Чудновский, М. (2008), Структура бычьих графов. I. Трехреберные пути с центрами и антицентрами (PDF).
  6. ^ Чудновский, М. (2008), Структура бычьих графов. II. Элементарные триграфы (PDF).
  7. ^ Чудновский, М. (2008), Структура бычьих графов. III. Глобальная структура (PDF).