Meredithin kreivi

Meredithin kreivi
Nimetty Guy Meredith
Huiput 70
kylkiluut 140
Halkaisija kahdeksan
Ympärysmitta 5
Automorfismit 38698352640
Kromaattinen numero 3
Kromaattinen indeksi 5
Ominaisuudet Euler
kirjan paksuus 3
Jonojen määrä 2
 Mediatiedostot Wikimedia Commonsissa

Meredith-graafi  on 4-säännöllinen suuntaamaton graafi , jossa on 70 kärkeä ja 140 reunaa, jonka Guy Meredith löysi vuonna 1973 [1] .

Meredith-graafi on yhdistetty 4-pisteisiin ja neljään reunaan yhdistetty . Sen kromaattinen luku on 3, kromaattinen indeksi 5, säde 7, halkaisija 8, ympärysmitta 4, eikä se ole Hamiltonin [2] . Kaaviossa on kirjan paksuus 3 ja jonojen määrä 2 [3] .

Vuonna 1973 julkaistu graafi tarjosi vastaesimerkin Crispin Nash-Williamsin olettamukselle, jonka mukaan mikä tahansa 4-säännöllinen vertex-4-liitetty graafi on aina Hamiltonin [4] [5] . Tatt kuitenkin osoitti, että kaikki 4-liitetyt tasograafit ovat Hamiltonin [6] .

Meredith-graafin ominaispolynomi on

.

Galleria

Muistiinpanot

  1. ↑ Weisstein, Eric W. Meredith  -kaavio Wolfram MathWorld -verkkosivustolla .
  2. ↑ Bondy JA, Murty USR Graph Theory. - Springer, 2007. - s. 470.
  3. ↑ Jessica Wolz, Lineaaristen asettelujen suunnittelu SAT:n kanssa . Diplomityö, Tübingenin yliopisto, 2018
  4. ↑ Meredith GHJ :n tavalliset 4-valenttiset 4-liitännät Ei-hamiltonilaiset ei-4-reunaiset värilliset kaaviot // J. Combin. Th.. - 1973. - Numero. B 14 . - S. 55-60 .
  5. ↑ Bondy JA, Murty USR Graph Theory with Applications. - New York: North Holland, 1976. - s. 239.
  6. ↑ Viimeaikaiset edistysaskeleet kombinatoriikassa / Tutte W. Literature T .. - New York: Academic Press, 1969.

Linkit