Граф Барнетта – Босака – Ледерберга
| Граф Барнетта – Босака – Ледерберга | |
|---|---|
 | |
| Вершины | 38 |
| Края | 57 |
| Радиус | 5 |
| Диаметр | 9 |
| Обхват | 4 |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Характеристики | Кубический Планарный Многогранник |
| Таблица графиков и параметров | |
В математической области теории графов граф Барнетта-Бозака-Ледерберга представляет собой кубический (то есть 3- правильный ) многогранный граф без гамильтонова цикла , наименьший возможный такой граф. [ 1 ] Он был открыт в середине 1960-х годов Джошуа Ледербергом , Дэвидом Барнеттом и Юрай Босаком, в честь которого он назван. Он имеет 38 вершин и 57 ребер. [ 2 ] [ 3 ] [ 4 ]
Другие более крупные негамильтоновы кубические многогранные графы включают граф Тутте с 46 вершинами и граф с 44 вершинами, найденный Эмануэлсом Гринбергсом с использованием теоремы Гринберга . Граф Барнетта-Босака-Ледерберга имеет конструкцию, аналогичную графу Тутте, но состоит из двух фрагментов Тутте, соединенных через пятиугольную призму , вместо трех, соединенных через тетраэдр . Без ограничения наличия ровно трех ребер в каждой вершине возможны гораздо меньшие по размеру негамильтоновы многогранные графы, включая граф Голднера – Харари и граф Гершеля .
Ссылки
[ редактировать ]- ^ Холтон, Д.А.; Маккей, Б.Д. (1988), «Наименьшие негамильтоновы 3-связные кубические плоские графы имеют 38 вершин», Journal of Combinatorial Theory, Series B , 45 (3): 305–319, doi : 10.1016/0095-8956 (88) )90075-5
- ^ Ледерберг, Джошуа (1967), «Цепи Гамильтона выпуклых трехвалентных многогранников (до 18 вершин)», The American Mathematical Monthly , 74 (5): 522–527, doi : 10.2307/2314879 , JSTOR 2314879 , MR 0211895
- ^ Босак, Дж. (1967), «Гамильтоновы линии в кубических графах», Теория графов (Международный симпозиум, Рим, 1966) , Нью-Йорк: Гордон и Брич, стр. 35–46, MR 0221970.
- ^ Вайсштейн, Эрик В. , «График Барнетта-Босака-Ледерберга» , MathWorld