En el campo matemático de la teoría de grafos , el gráfico de Barnette-Bosák-Lederberg es un gráfico poliédrico cúbico (es decir, 3- regular ) sin ciclo hamiltoniano , el gráfico más pequeño posible. [1] Fue descubierto a mediados de la década de 1960 por Joshua Lederberg , David Barnette y Juraj Bosák, de quienes lleva el nombre. Tiene 38 vértices y 57 aristas. [2] [3] [4]
Otros gráficos poliédricos cúbicos no hamiltonianos más grandes incluyen el gráfico de Tutte de 46 vértices y un gráfico de 44 vértices encontrado por Emanuels Grīnbergs utilizando el teorema de Grinberg . El gráfico de Barnette-Bosák-Lederberg tiene una construcción similar al gráfico de Tutte pero está compuesto por dos fragmentos de Tutte, conectados a través de un prisma pentagonal , en lugar de tres conectados a través de un tetraedro . Sin la restricción de tener exactamente tres aristas en cada vértice, son posibles gráficos poliédricos no hamiltonianos mucho más pequeños, incluidos el gráfico de Goldner-Harary y el gráfico de Herschel .