Вальтер граф
| Вальтер граф | |
|---|---|
 Вальтер граф | |
| Назван в честь | Хансйоахим Вальтер |
| Вершины | 25 |
| Края | 31 |
| Радиус | 5 |
| Диаметр | 8 |
| Обхват | 3 |
| Автоморфизм | 1 |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Характеристики | двусторонний Планарный |
| Таблица графиков и параметров | |
В математической области теории графов граф Вальтера , также называемый фрагментом Тутте , представляет собой плоский двудольный граф с 25 вершинами и 31 ребром, названный в честь Хансйоахима Вальтера . [ 1 ] Он имеет хроматический индекс 3, обхват 3 и диаметр 8.
Если удалить единственную вершину степени 1, сосед которой имеет степень 3, в полученном графе не будет гамильтонова пути . Это свойство использовалось Тутте при объединении трёх графов Вальтера для создания графа Тутте , [ 2 ] первый известный контрпример к гипотезе Тейта о том, что каждый 3-правильный многогранник имеет гамильтонов цикл. [ 3 ]
Алгебраические свойства
[ редактировать ]Граф Вальтера является тождественным графом; его группа автоморфизмов является тривиальной группой .
Характеристический полином графа Вальтера:
Ссылки
[ редактировать ]- ^ Вайсштейн, Эрик В. «Вальтер Граф» . Математический мир .
- ^ Тутте, WT (1946), «О гамильтоновых схемах» (PDF) , Журнал Лондонского математического общества , 21 (2): 98–101, doi : 10.1112/jlms/s1-21.2.98
- ^ Тейт, П.Г. Листинга (1884), « Топология », Философский журнал , 5-я серия, 17 : 30–46 . Перепечатано в научных статьях , Vol. II, стр. 85–98.
 | Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |