Бычий график
| Бычий график | |
|---|---|
 Бычий график | |
| Вершины | 5 |
| Края | 5 |
| Радиус | 2 |
| Диаметр | 3 |
| Обхват | 3 |
| Автоморфизм | 2 ( З /2 З ) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Характеристики | Планарный Расстояние единицы |
| Таблица графиков и параметров | |
В математической области теории графов представляет бычий граф собой плоский неориентированный граф с 5 вершинами и 5 ребрами, имеющий форму треугольника с двумя непересекающимися висячими ребрами. [1]
Он имеет хроматическое число 3, хроматический индекс 3, радиус 2, диаметр 3 и обхват 3. Это также самодополняющий граф , блочный граф , расщепленный граф , интервальный граф , граф без когтей , 1- вершинный граф. -связный граф и 1- реберно-связный граф .
Графики без быков
[ редактировать ]Граф является свободным от быков, если в нем нет быков в качестве индуцированного подграфа . Графы без треугольников — это графы без быков, поскольку каждый бык содержит треугольник. Теорема о сильном совершенном графе была доказана для графов без быков задолго до ее доказательства для общих графов. [2] Известен алгоритм распознавания полиномиального времени для совершенных графов без быков. [3]
Мария Чудновский и Шмуэль Сафра изучили графы без быков в более общем плане, показав, что любой такой граф должен иметь либо большую клику , либо большое независимое множество (т. е. гипотеза Эрдеша-Хайнала ). для бычьего графа справедлива [4] и разработка общей теории структуры этих графов. [5] [6] [7]
Хроматический и характеристический полином
[ редактировать ]
Хроматический полином бычьего графа равен . Два других графика хроматически эквивалентны бычьему графу.
Его характеристический полином .
Его полином Тутте равен .
Ссылки
[ редактировать ]- ^ Вайсштейн, Эрик В. «Бычий график» . Математический мир .
- ^ Хватал, В. ; Сбихи, Н. (1987), «Графы Берджа без быков идеальны», Graphs and Combinatorics , 3 (1): 127–139, doi : 10.1007/BF01788536 , S2CID 44570627 .
- ^ Рид, Б .; Сбихи, Н. (1995), «Распознавание совершенных графов без быков», Graphs and Combinatorics , 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) .