Английская Википедия:Barnette–Bosák–Lederberg graph

Материал из Онлайн справочника
Версия от 12:48, 6 февраля 2024; EducationBot (обсуждение | вклад) (Новая страница: «{{Английская Википедия/Панель перехода}} {{Short description|Non-Hamiltonian simple polyhedron}} {{infobox graph | image = File:Barnette-Bosak-Lederberg graph (Lombardi drawing).svg | name = Barnette–Bosák–Lederberg graph | vertices = 38 | edges = 57 | automorphisms = | girth = 4 | radius = 5 | diameter = 9 | chromatic_number = 3 | chromatic_index = 3 | properties = Cubic<br>Planar graph|Pla...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

Шаблон:Short description Шаблон:Infobox graph In the mathematical field of graph theory, the Barnette–Bosák–Lederberg graph is a cubic (that is, 3-regular) polyhedral graph with no Hamiltonian cycle, the smallest such graph possible.[1] It was discovered in the mid-1960s by Joshua Lederberg, David Barnette, and Juraj Bosák, after whom it is named. It has 38 vertices and 57 edges.[2][3][4]

Other larger non-Hamiltonian cubic polyhedral graphs include the 46-vertex Tutte graph and a 44-vertex graph found by Emanuels Grīnbergs using Grinberg's theorem. The Barnette–Bosák–Lederberg graph has a similar construction to the Tutte graph but is composed of two Tutte fragments, connected through a pentagonal prism, instead of three connected through a tetrahedron. Without the constraint of having exactly three edges at every vertex, much smaller non-Hamiltonian polyhedral graphs are possible, including the Goldner–Harary graph and the Herschel graph.

References

Шаблон:Reflist