Contele de Grey

Graficul Gray  este un graf bipartit nedirecționat cu 54 de vârfuri și 81 de muchii. Graficul este cubic  - orice vârf aparține exact trei muchii. Graficul a fost descoperit de Gray în 1932 (fără publicare), apoi descoperit independent de Bouwer în 1968, ca răspuns la o întrebare pusă de Folkman în 1967. Graficul Gray este notabil ca fiind primul exemplu istoric de grafic cubic care are proprietatea algebrică a muchiei, dar nu a tranzitivității la vârf.

Numărul cromatic al graficului Gray este 2, indicele cromatic  este 3, iar raza și diametrul sunt 6. Este, de asemenea, un graf neplanar conectat cu 3 vârfuri și conectat cu 3 muchii .

Clădire

Graficul Gray poate fi construit [1] din 27 de puncte ale unei rețele de 3×3×3 și 27 de linii paralele cu axele și care trec prin aceste puncte. Acest set de puncte și linii formează o configurație proiectivă  - exact trei linii trec prin fiecare punct și exact trei puncte se află pe fiecare linie. Graficul Gray este graficul Levi al acestei configurații. Graficul are un vârf pentru fiecare punct și pentru fiecare linie din această configurație și o muchie pentru fiecare pereche punct-linie dacă punctul se află pe linie. Această construcție poate fi generalizată (Bauwer 1972) la orice dimensiune , dând grafii Lévy cu valență cu proprietăți algebrice similare cu cele ale grafului Gray.

De asemenea, poate fi construit ca un graf Levi pentru muchiile și fețele triunghiulare ale unor 4-politop regulați abstracti toroidali local [2] .

Marusic și Pisanski [3] au oferit câteva metode alternative pentru construirea unui graf Gray. Ca orice alt graf bipartit, graficul Gray nu conține cicluri de lungime impară și nici cicluri cu patru sau șase vârfuri, deci circumferința unui graf Gray este 8. Cea mai simplă suprafață orientată în care poate fi încorporat un graf Gray este de genul 7 [4] .

Graficul Gray este hamiltonian și poate fi construit din notația LCF :

Proprietăți algebrice

Grupul de automorfisme al grafului Gray este un grup de ordinul 1296. Acționează tranzitiv asupra muchiilor grafului, dar nu și asupra vârfurilor acestuia - există automorfisme care duc orice muchie la orice altă muchie, dar nu există automorfisme care să ia orice muchie. vârf la oricare altul. Nodurile corespunzătoare configurației care stau la baza graficului pot fi simetrice numai vârfurilor corespunzătoare punctelor de configurare, iar vârfurile corespunzătoare liniilor sunt simetrice numai vârfurilor corespunzătoare liniilor. Astfel, graficul Gray este un grup semisimetric și este cel mai mic grafic cubic semisimetric posibil.

Polinomul caracteristic al graficului Gray este:

Galerie

• Contele de Grey

• Numărul cromatic al lui Count Gray este 2.

• indicele cromatic al graficului Gray este 3.

• Configurația care stă la baza Graph Gray.

Note

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

Link -uri

• Un grafic cubic tranzitiv de muchie, dar nu de vârf // Buletinul Societății Canadei de Matematică. - 1968. - T. 11 . — S. 533–535 . - doi : 10.4153/CMB-1968-063-0 . .
• IZ Bouwer. Grafice regulate tranzitive pe muchie, dar nu pe vârf // Journal of Combinatorial Theory, Seria B. - 1972. - Vol. 12 . — S. 32–40 . - doi : 10.1016/0095-8956(72)90030-5 . .
• J Folkman. Grafice linie simetrice regulate // Journal of Combinatorial Theory. - 1967. - T. 3 , nr. 3 . — S. 533–535 . - doi : 10.1016/S0021-9800(67)80069-3 . .
• Dragan Marušic, Tomaž Pisanski. Graficul Gray revizuit  // 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. Genul grafului Gray este 7 // European Journal of Combinatorics. - 2005. - T. 26 , nr. 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, Seria A. - 2007. - Vol. 114 , nr. 3 . — S. 421–435 . - doi : 10.1016/j.jcta.2006.06.007 .
• Weisstein, Eric W. Gray Graph  (engleză) pe site-ul web Wolfram MathWorld .
• Graficul gri este cel mai mic grafic de acest fel Arhivat 22 februarie 2014 la Wayback Machine , de la MathWorld .