En el campo matemático de la teoría de grafos , el grafo de Barnette–Bosák–Lederberg es un grafo poliédrico cúbico (es decir, 3- regular ) sin ciclo hamiltoniano , el grafo más pequeño posible de este tipo. [1] Fue descubierto a mediados de la década de 1960 por Joshua Lederberg , David Barnette y Juraj Bosák, de quien recibe su nombre. Tiene 38 vértices y 57 aristas. [2] [3] [4]
Otros grafos poliédricos cúbicos no hamiltonianos más grandes incluyen el grafo de Tutte de 46 vértices y un grafo de 44 vértices encontrado por Emanuels Grīnbergs usando el teorema de Grinberg . El grafo de Barnette–Bosák–Lederberg tiene una construcción similar al grafo de Tutte pero está compuesto de 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 grafos poliédricos no hamiltonianos mucho más pequeños, incluyendo el grafo de Goldner–Harary y el grafo de Herschel .