Klec Balaban 11 - Balaban 11-cage
| Klec Balaban 11 | |
|---|---|
 Klec Balaban 11 | |
| Pojmenoval podle | Alexandru T. Balaban |
| Vrcholy | 112 |
| Hrany | 168 |
| Poloměr | 6 |
| Průměr | 8 |
| Obvod | 11 |
| Automorfismy | 64 |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti | Krychlový Klec Hamiltonian |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Klec Balaban 11 nebo Klec Balaban (3-11) je 3-běžný graf se 112 vrcholy a 168 hranami pojmenovanými podle Alexandru T. Balaban.[1]
Klec Balaban 11 je jedinečná (3-11) -klec. Objevil ji Balaban v roce 1973.[2] Jedinečnost byla prokázána Brendan McKay a Wendy Myrvoldová v roce 2003.[3]
Klec Balaban 11 je Hamiltonovský graf a mohou být konstruovány excizí z Tutte 12-klec odstraněním malého podstromu a potlačením výsledných vrcholů stupně dva.[4]
Má číslo nezávislosti 52,[5] chromatické číslo 3, chromatický index 3, poloměr 6, průměr 8 a obvod 11. Je to také 3graf spojený s vrcholem a 3-hranový graf.
Algebraické vlastnosti
The charakteristický polynom klece Balaban 11: .
Automorfická skupina klece Balaban 11 je řádu 64.[4]
Galerie
The chromatické číslo klece Balaban 11 je 3.
The chromatický index klece Balaban 11 je 3.
Alternativní výkres klece Balaban 11.[6]
Reference
- ^ Weisstein, Eric W. „Balaban 11-Cage“. MathWorld.
- ^ Balaban, Alexandru T., Trojmocné grafy obvodu devíti a jedenácti a vztahy mezi klecemi„Revue Roumaine de Mathématiques Pures et Appliquées 18 (1973), 1033-1043. PAN0327574
- ^ Weisstein, Eric W. "Graf klece". MathWorld.
- ^ A b Geoffrey Exoo a Robert Jajcay, průzkum dynamické klece, Electr. J. Combin. 15 (2008)
- ^ Maher Heal (2016)
- ^ P. Eades, J. Marks, P. Mutzel, North. „Zpráva o soutěži Graph-drawing“, TR98-16, prosinec 1998, Mitsubishi Electric Research Laboratories.
Reference
- Heal, Maher (2016), „Kvadratická programová formulace k nalezení maximální nezávislé množiny libovolného grafu“, Mezinárodní konference o výpočetní vědě a výpočetní inteligenci 2016, Las Vegas: IEEE Computer Society