Meredithův graf - Meredith graph

Meredithův graf
Meredith graph.svg
Meredithův graf
Pojmenoval podleG. H. Meredith
Vrcholy70
Hrany140
Poloměr7
Průměr8
Obvod4
Automorfismy38698352640
Chromatické číslo3
Chromatický index5
Tloušťka knihy3
Číslo fronty2
VlastnostiEulerian
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

Reference

  1. ^ Weisstein, Eric W. "Meredithův graf". MathWorld.
  2. ^ Bondy, J. A. a Murty, USA „Teorie grafů“. Springer, str. 470, 2007.
  3. ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
  4. ^ Meredith, G. H. J. „Pravidelné 4-valentové 4-připojené nehamiltonovské non-4-hrany-barevné barvy.“ J. Combin. Čt. B 14, 55-60, 1973.
  5. ^ Bondy, J. A. a Murty, U. S. R. „Teorie grafů s aplikacemi“. New York: Severní Holandsko, str. 239, 1976.
  6. ^ Tutte, W.T., ed., Nedávný pokrok v kombinatorice. Academic Press, New York, 1969.