Contele Pappa

În teoria grafurilor, un graf Pappus este un graf bipartit 3 - graf regulat nedirecționat cu 18 vârfuri și 27 de muchii, care este un graf Levi al configurației Pappus [1] . Este numit după Pappus din Alexandria , un matematician antic grec care credea că a demonstrat „teorema hexagonului” în care Pappus a descris configurația. Sunt cunoscute toate graficele distanțe cubice -regulate. Contele Pappa este unul dintre cele treisprezece astfel de conți [2] .

Numărul de încrucișări rectilinii ale unui grafic Pappus este 5, iar acest grafic este cel mai mic grafic cubic cu acel număr de încrucișări (secvența A110507 în OEIS ). Graficul are circumferința 6, diametrul 4, raza 4, numărul cromatic 2, indicele cromatic 3 și este atât legat de 3 vârfuri, cât și de 3 muchii .

Polinomul cromatic al graficului Pappus este .

Numele de „graf Pappa” este folosit și pentru un grafic apropiat cu nouă vârfuri [3] , câte un vârf pentru fiecare punct al configurației Pappus, cu muchii pentru fiecare pereche de puncte care se află pe aceeași linie. Acest grafic este 6-regular și este complementul uniunii a trei grafice triunghiulare neînrudite . Primul graf Pappus poate fi încorporat într-un tor, obținându-se astfel o hartă obișnuită cu nouă fețe hexagonale. Al doilea grafic formează, cu această încorporare, o hartă obișnuită cu 18 fețe triunghiulare.

Proprietăți algebrice

Grupul de automorfism al unui graf Pappus este un grup cu ordinul 216. Acționează tranzitiv asupra vârfurilor și muchiilor grafului. Astfel, graficul Pappus este simetric . Are automorfisme care mapează orice vârf la orice alt și orice muchie la orice altă muchie. În lista lui Foster, graficul lui Papa este etichetat F018A și este singurul grafic cubic simetric cu 18 vârfuri [4] [5] .

Polinomul caracteristic al graficului Pappus este . Acesta este singurul grafic cu un astfel de polinom caracteristic, deci în acest caz graficul este definit de spectrul său.

Galerie

• Graficul Pappa, colorat pentru a evidenția diferitele cicluri.

• indicele cromatic al graficului Pappus este 3.

• Numărul cromatic al contelui Pappus este 2.

Note

1. ^ Weisstein , Eric W. Pappus Graph  pe site- ul Wolfram MathWorld .
2. ↑ Brouwer, AE; Cohen, A. M.; și Neumaier, A. Distanța — Grafice regulate. New York: Springer-Verlag, 1989.
3. ↑ ÎN Kagno. Graficele lui Desargues și Pappus și grupurile lor. — Jurnalul American de Matematică. - The Johns Hopkins University Press, 1947. - V. 69. - S. 859-863. - doi : 10.2307/2371806 .
4. ↑ Royle, G. „Cubic Symmetric Graphs (The Foster Census).” Arhivat din original pe 20 iulie 2008.
5. ↑ Conder, M. și Dobcsányi, P. „Trivalent Symmetric Graphs Up to 768 Vertices”. J. Combin. Matematică. Combina. Calculator. 40, 41-63, 2002.