Meredith grófja

Meredith grófja
Valaki után elnevezve Guy Meredith
Csúcsok 70
borda 140
Átmérő nyolc
Heveder 5
Automorfizmusok 38698352640
Kromatikus szám 3
Kromatikus index 5
Tulajdonságok Euler
könyv vastagsága 3
Sorok száma 2
 Médiafájlok a Wikimedia Commons oldalon

A Meredith gráf  egy 4 szabályos irányítatlan gráf , 70 csúcsgal és 140 éllel, Guy Meredith fedezte fel 1973-ban [1] .

A Meredith gráf 4 csúcshoz és 4 élhez kapcsolódik . Kromatikus száma 3 , kromatikus indexe 5, sugara 7, átmérője 8, kerülete 4, és nem Hamilton -féle [2] . A gráf könyvvastagsága 3, a sorok száma pedig 2 [3] .

Az 1973-ban publikált gráf ellenpéldát adott Crispin Nash-Williams sejtésére, miszerint bármely 4-reguláris csúcs-4-összefüggésű gráf mindig Hamilton-féle [4] [5] . Tatt azonban kimutatta, hogy minden 4-összefüggésű síkgráf Hamilton -féle [6] .

A Meredith-gráf karakterisztikus polinomja az

.

Galéria

Jegyzetek

  1. ↑ Weisstein, Eric W. Meredith grafikonja  a Wolfram MathWorld webhelyen .
  2. ↑ Bondy JA, Murty USR Graph Theory. - Springer, 2007. - 470. o.
  3. ↑ Jessica Wolz, Lineáris elrendezések tervezése SAT segítségével . Mesterdolgozat, Tübingeni Egyetem, 2018
  4. ↑ Meredith GHJ normál, 4 vegyértékű 4 összekapcsolt, nem hamiltoni nem 4 élű színezhető grafikonok // J. Combin. Th.. - 1973. - Issue. B 14 . - S. 55-60 .
  5. ↑ Bondy JA, Murty USR Graph Theory with Applications. - New York: North Holland, 1976. - 239. o.
  6. ↑ Recent Progress in Combinatorics / Tutte W. Literature T .. - New York: Academic Press, 1969.

Linkek