Graf Barnette – Bosák – Lederberg - Barnette–Bosák–Lederberg graph - Wikipedia
| Graf Barnette – Bosák – Lederberg | |
|---|---|
 | |
| Vrcholy | 38 |
| Hrany | 57 |
| Poloměr | 5 |
| Průměr | 9 |
| Obvod | 4 |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti | Krychlový Rovinný Mnohostěnný |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Graf Barnette – Bosák – Lederberg je krychlový (tj. 3pravidelný ) polyedrický graf bez č Hamiltonovský cyklus, nejmenší možný graf.[1] Bylo objeveno v polovině 60. let 20. století Joshua Lederberg, David Barnette a Juraj Bosák, podle nichž je pojmenován. Má 38 vrcholů a 69 okrajů.[2][3][4]
Mezi další větší nehamiltonovské kubické polyedrické grafy patří vrchol 46 Tutte graph a 44-vertexový graf nalezen Emanuels Grīnbergs použitím Grinbergova věta. Barnette – Bosák – Lederbergův graf má podobnou konstrukci jako Tutteův graf, ale skládá se ze dvou Tutteových fragmentů spojených prostřednictvím pětiúhelníkový hranol, místo tří připojených přes a čtyřstěn Bez omezení mít přesně tři hrany na každém vrcholu jsou možné mnohem menší nehamiltonovské polyedrické grafy, včetně Goldner – Hararyův graf a Herschelův graf.
Reference
- ^ Holton, D. A .; McKay, B. D. (1988), „Nejmenší nehamiltonovské 3 spojené kubické planární grafy mají 38 vrcholů“, Journal of Combinatorial Theory, Series B, 45 (3): 305–319, doi:10.1016/0095-8956(88)90075-5
- ^ Lederberg, Joshua (1967), „Hamiltonovy obvody konvexních trojmocných mnohostěnů (až 18 vrcholů)“, Americký matematický měsíčník, 74: 522–527, doi:10.2307/2314879, PAN 0211895
- ^ Bosák, J. (1967), „hamiltonovské čáry v kubických grafech“, Theory of Graphs (Internat. Sympos., Řím, 1966), New York: Gordon and Breach, s. 35–46, PAN 0221970
- ^ Weisstein, Eric W. „Graf Barnette-Bosák-Lederberg“. MathWorld.