Earl of Grey

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 .

Épület

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ő :

Algebrai tulajdonságok

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 :

Galéria

• 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ó.

Jegyzetek

1. ↑ Bouwer, 1972 .
2. ↑ Monson, Pisanski, Schulte, Ivic-Weiss, 2007 .
3. ↑ Marusic, Pisanski, 2000 .
4. ↑ Marušič, Pisanski, Wilson, 2005 .

Linkek

• Egy él, de nem csúcs tranzitív köbös gráf // Bulletin of the Canadian Mathematical Society. - 1968. - T. 11 . – S. 533–535 . - doi : 10.4153/CMB-1968-063-0 . .
• IZ Bouwer. Élen, de nem csúcson tranzitív reguláris gráfokon // Journal of Combinatorial Theory, Series B. - 1972. - Vol. 12 . — S. 32–40 . - doi : 10.1016/0095-8956(72)90030-5 . .
• J Folkman. Szabályos vonalszimmetrikus gráfok // Journal of Combinatorial Theory. - 1967. - T. 3 , szám. 3 . – S. 533–535 . - doi : 10.1016/S0021-9800(67)80069-3 . .
• Dragan Marušic, Tomaž Pisanski. A Gray-gráf újralátogatása  // Journal of Graph Theory. - 2000. - T. 35 . – S. 1–7 . - doi : 10.1002/1097-0118(200009)35:1<1::AID-JGT1>3.0.CO;2-7 . .
• Dragan Marusic, Tomaž Pisanski, Steve Wilson. A Gray gráf nemzetsége 7 // European Journal of Combinatorics. - 2005. - T. 26 , sz. 3–4 . – S. 377–385 . - doi : 10.1016/j.ejc.2004.01.015 . .
• B. Monson, T. Pisanski, E. Schulte, A. Ivic-Weiss. Semisymmetric Graphs from Polytopes // Journal of Combinatorial Theory, Series A. - 2007. - Vol. 114 , no. 3 . – S. 421–435 . - doi : 10.1016/j.jcta.2006.06.007 .
• Weisstein, Eric W. Gray Graph  (angol) a Wolfram MathWorld webhelyén .
• A szürke grafikon a maga nemében a legkisebb grafikon archiválva 2014. február 22-én a Wayback Machine -nél , a MathWorldtől .