Earl of Grey | |
---|---|
Valaki után elnevezve | Marion Cameron Gray |
Csúcsok | 54 |
borda | 81 |
Sugár | 6 |
Átmérő | 6 |
Heveder | nyolc |
Automorfizmusok | 1296 |
Kromatikus szám | 2 |
Kromatikus index | 3 |
Tulajdonságok |
hamiltoni |
Médiafájlok a Wikimedia Commons oldalon |
A Gray gráf egy kétoldalú irányítatlan gráf , 54 csúcsával és 81 élével. A gráf köbös - bármely csúcs pontosan három élhez tartozik. A grafikont Gray fedezte fel 1932 -ben (közzététel nélkül), majd Bouwer fedezte fel függetlenül 1968-ban, válaszul Folkman 1967-ben feltett kérdésére. A Gray gráf történelmileg az első példa egy olyan köbös gráfra, amely rendelkezik az él algebrai tulajdonságával, de nem a csúcstranzitivitással.
A Gray gráf kromatikus száma 2, a kromatikus indexe 3, a sugara és átmérője pedig 6. Ez egy 3 csúcshoz kapcsolódó és 3 élhez kapcsolódó nem síkbeli gráf is .
A Gray-gráf [1] egy 3×3×3-as rács 27 pontjából és 27, a tengelyekkel párhuzamos és ezeken a pontokon áthaladó egyenesből készíthető. Ez a pont- és vonalhalmaz egy projektív konfigurációt alkot – pontosan három egyenes halad át minden ponton, és pontosan három pont van mindegyik egyenesen. A Gray -gráf ennek a konfigurációnak a Levi-gráfja. A gráfnak van egy csúcsa ennek a konfigurációnak minden pontjához és minden vonalához, és minden pont-vonal párhoz egy éle, ha a pont az egyenesen fekszik. Ez a konstrukció bármely dimenzióra általánosítható (Bauwer 1972) , így -valence Lévy-gráfokat kapunk, amelyek algebrai tulajdonságai hasonlóak a Gray-gráféhoz.
Levi-gráfként is megszerkeszthető néhány lokálisan toroidális absztrakt szabályos 4-politóp éleire és háromszöglapjaira [2] .
Marusic és Pisanski [3] adott néhány alternatív módszert Gray-gráf megalkotására. Mint minden más kétrészes gráf, a Gray-gráf sem tartalmaz páratlan hosszúságú ciklusokat , sem négy vagy hat csúcsú ciklusokat, így egy Gray-gráf kerülete 8. A legegyszerűbb orientált felület, amelybe Gray gráf beágyazható. a 7. nemzetségbe tartozik [4] .
A Gray-gráf Hamilton -féle , és az LCF-jelölésből szerkeszthető :
.A Gray gráf automorfizmuscsoportja egy 1296-os rendű csoport. Tranzitívan hat a gráf éleire, de nem a csúcsaira - vannak olyan automorfizmusok, amelyek bármelyik élt bármely másik élre vinnék, de nincsenek olyan automorfizmusok, amelyek bármilyen élt vesznek fel. csúcs bármely máshoz. A gráf alapjául szolgáló konfigurációnak megfelelő csúcsok csak a konfigurációs pontoknak megfelelő csúcsokra lehetnek szimmetrikusak, a vonalaknak megfelelő csúcsok pedig csak az egyeneseknek megfelelő csúcsokra. Így a Gray gráf egy félszimmetrikus csoport , és a lehető legkisebb köbös félszimmetrikus gráf.
A Gray-gráf karakterisztikus polinomja :
Earl of Grey
A Count Gray kromatikus száma 2.
a Gray-gráf kromatikus indexe 3.
A Graph Gray alapjául szolgáló konfiguráció.