Hrabě z Meredith
| hrabě z Meredith | |
|---|---|
| Pojmenoval podle | Guy Meredith |
| Vrcholy | 70 |
| žebra | 140 |
| Průměr | osm |
| obvod | 5 |
| Automorfismy | 38698352640 |
| Chromatické číslo | 3 |
| Chromatický index | 5 |
| Vlastnosti | Euler |
| tloušťka knihy | 3 |
| Počet front | 2 |
| Mediální soubory na Wikimedia Commons | |
Meredithův graf je 4-pravidelný neorientovaný graf se 70 vrcholy a 140 hranami, který objevil Guy Meredith v roce 1973 [1] .
Meredithův graf je spojen 4 vrcholy a 4 hranami . Má chromatické číslo 3, chromatický index 5, poloměr 7, průměr 8, obvod 4 a není hamiltonovský [2] . Graf má tloušťku knihy 3 a počet front 2 [3] .
Tento graf, publikovaný v roce 1973, poskytl protipříklad k domněnce Crispina Nashe-Williamse, že jakýkoli 4-pravidelný vertex-4-souvislý graf je vždy hamiltonovský [4] [5] . Tatt však ukázal, že všechny 4-souvislé rovinné grafy jsou hamiltonovské [6] .
Charakteristickým polynomem Meredithova grafu je
.
Galerie
-
Chromatické číslo hraběte z Meredith je 3.
-
Chromatický index hraběte z Meredith je 5.
Poznámky
- ↑ Weisstein, Eric W. Meredith graf na webu Wolfram MathWorld .
- ↑ Bondy JA, Murty USR Graph Theory. - Springer, 2007. - S. 470.
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT . Diplomová práce, Univerzita v Tübingenu, 2018
- ↑ Meredith GHJ Regular 4-valent 4-connected Non-hamiltonian Non-4-Edge-Colorable Graphs // J. Combin. Čt.. - 1973. - Vydání. B 14 . - S. 55-60 .
- ↑ Bondy JA, Murty USR Graph Theory with Applications. - New York: Severní Holandsko, 1976. - S. 239.
- ↑ Nedávný pokrok v kombinatorice / Tutte W. Literatura T .. - New York: Academic Press, 1969.
Odkazy
- Web AE Brouwera: The Armanios-Wells graph Archivováno 14. dubna 2018 na Wayback Machine