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