11článkový Balaban
| 11článkový Balaban | |
|---|---|
| 11článkový Balaban | |
| Pojmenoval podle | Alexandru T. Balabana |
| Vrcholy | 112 |
| žebra | 168 |
| Poloměr | 6 |
| Průměr | osm |
| obvod | jedenáct |
| Automorfismy | 64 |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti |
Kubická hamiltonovská klec |
| Mediální soubory na Wikimedia Commons | |
11-buněčný Balaban nebo (3-11)-cell Balaban je 3- pravidelný graf se 112 vrcholy a 168 hranami, pojmenovaný po rumunském chemikovi Alexandru T. Balabanovi [1] .
Balabanova 11-buňka je jediná (3-11)-buňka . Hrabě objevil Balaban v roce 1973 [2] . Jeho jedinečnost prokázali Brendan McKay a Wendy Myhrvold v roce 2003 [3] .
Vlastnosti
Balabanova 11-buňka je hamiltonovský graf a může být sestaven odstraněním malého podstromu z Tuttovy 12-buňky a výsledných vrcholů stupně dva [4] .
Graf má číslo nezávislosti 52 [5] , chromatické číslo 3, chromatický index 3, poloměr 6, průměr 8 a obvod 11. Je také 3-vrcholově spojený a 3-hranný připojený graf.
Algebraické vlastnosti
Charakteristický polynom Balabanovy 11článkové buňky je: .
Skupina automorfismu grafu má řád 64 [4] .
Galerie
-
Chromatické číslo Balabanova 11článku je 3.
-
Chromatický index Balabanovy 11článkové buňky je 3.
-
Alternativní kresba Balabanovy 11článkové [6]
Poznámky
- ↑ Weisstein, Eric W. Balaban 11-Cage na webu Wolfram MathWorld .
- ↑ Balaban, 1973 , str. 1033-1043.
- ↑ Weisstein, Eric W. Cage Graph na webu Wolfram MathWorld .
- ↑ 1 2 Exoo, Jajcay, 2008 .
- ↑ Uzdrav, 2016 .
- ↑ Eades, Marks, Mutzel, North, 1998 .
Literatura
- Alexandru T. Balaban. Trivalentní grafy obvodu devět a jedenáct a vztahy mezi klecemi // Revue Roumaine de Mathématiques Pures et Appliquées. - 1973. - T. 18.
- Geoffrey Exoo, Robert Jajcay. Dynamický průzkum klecí // Elektr. J. Combin .. - 2008. - Vydání. 15 .
- Maher Heal. Formulace kvadratického programování k nalezení maximální nezávislé sady jakéhokoli grafu // Mezinárodní konference o výpočetní vědě a výpočetní inteligenci v roce 2016. — Las Vegas: IEEE Computer Society , 2016.
- Eades P., Marks J., Mutzel P., North S. Graph-Drawing Contest Report // TR98-16. - Mitsubishi Electric Research Laboratories, 1998.