Meredithův graf - Meredith graph
| Meredithův graf | |
|---|---|
 Meredithův graf | |
| Pojmenoval podle | G. H. Meredith |
| Vrcholy | 70 |
| Hrany | 140 |
| Poloměr | 7 |
| Průměr | 8 |
| Obvod | 4 |
| Automorfismy | 38698352640 |
| Chromatické číslo | 3 |
| Chromatický index | 5 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Eulerian |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Meredithův graf je 4-pravidelný neorientovaný graf se 70 vrcholy a 140 hranami objevenými Guyem H. J. Meredithem v roce 1973.[1]
Meredithův graf je 4připojen k vrcholu a 4-připojeno k okraji, má chromatické číslo 3, chromatický index 5, poloměr 7, průměr 8, obvod 4 a je ne-hamiltonovský.[2] Má to tloušťka knihy 3 a číslo fronty 2.[3]
Publikováno v roce 1973 poskytuje protiklad k Crispin Nash-Williams domněnka, že každý 4-pravidelný 4-vrchol spojený graf je Hamiltonian.[4][5] Nicméně, W. T. Tutte ukázal, že všechny 4 připojené rovinné grafy jsou hamiltonovci.[6]
The charakteristický polynom Meredithova grafu je .
Galerie
The chromatické číslo Meredithova grafu je 3.
The chromatický index Meredithova grafu je 5.
Reference
- ^ Weisstein, Eric W. "Meredithův graf". MathWorld.
- ^ Bondy, J. A. a Murty, USA „Teorie grafů“. Springer, str. 470, 2007.
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Meredith, G. H. J. „Pravidelné 4-valentové 4-připojené nehamiltonovské non-4-hrany-barevné barvy.“ J. Combin. Čt. B 14, 55-60, 1973.
- ^ Bondy, J. A. a Murty, U. S. R. „Teorie grafů s aplikacemi“. New York: Severní Holandsko, str. 239, 1976.
- ^ Tutte, W.T., ed., Nedávný pokrok v kombinatorice. Academic Press, New York, 1969.