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.