Greve Pappa

I grafteori er en Pappus-graf en todelt 3 - regulær urettet graf med 18 hjørner og 27 kanter, som er en Levi-graf af Pappus-konfigurationen [1] . Det er opkaldt efter Pappus af Alexandria , en oldgræsk matematiker , der mente, at han havde bevist "hexagon-sætningen", hvori Pappus beskrev konfigurationen. Alle kubikafstand -regulære grafer er kendte. Grev Pappa er en af ​​tretten sådanne grever [2] .

Antallet af retlinede krydsninger af en Pappus-graf er 5, og denne graf er den mindste kubiske graf med det antal krydsninger (sekvens A110507 i OEIS ). Grafen har omkreds 6, diameter 4, radius 4, kromatisk nummer 2, kromatisk indeks 3, og er både 3-kant-forbundet og 3-kant-forbundet .

Det kromatiske polynomium i Pappus-grafen er .

Navnet "Pappa-graf" bruges også til en tæt graf med ni toppunkter [3] , et toppunkt for hvert punkt i Pappus-konfigurationen, med kanter for hvert par punkter, der er på samme linje. Denne graf er 6-regulær og er komplementet til foreningen af ​​tre ikke-relaterede trekantede grafer . Den første Pappus-graf kan indlejres i en torus og dermed opnå et regulært kort med ni sekskantede flader. Den anden graf danner med denne indlejring et regulært kort med 18 trekantede flader.

Algebraiske egenskaber

Automorfigruppen i en Pappus-graf er en gruppe med orden 216. Den virker transitivt på grafens spidser og kanter. Således er Pappus-grafen symmetrisk . Den har automorfismer, der kortlægger enhver top til enhver anden og enhver kant til enhver anden kant. I Fosters liste er Papas graf mærket F018A og er den eneste kubiske symmetriske graf med 18 hjørner [4] [5] .

Det karakteristiske polynomium i Pappus-grafen er . Dette er den eneste graf med et så karakteristisk polynomium, så i dette tilfælde er grafen defineret af sit spektrum.

Galleri

• Pappa-grafen, farvet for at fremhæve de forskellige cyklusser.

• det kromatiske indeks for Pappus-grafen er 3.

• Grev Pappus ' kromatiske tal er 2.

Noter

1. ↑ Weisstein, Eric W. Pappus Graf  på Wolfram MathWorld- webstedet .
2. ↑ Brouwer, AE; Cohen, A.M.; og Neumaier, A. Afstand — Regelmæssige Grafer. New York: Springer-Verlag, 1989.
3. ↑ I Kagno. Desargues' og Pappus' grafer og deres grupper. — American Journal of Mathematics. - The Johns Hopkins University Press, 1947. - V. 69. - S. 859-863. - doi : 10.2307/2371806 .
4. ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arkiveret fra originalen den 20. juli 2008.
5. ↑ Conder, M. og Dobcsányi, P. "Trivalente symmetriske grafer op til 768 hjørner." J. Combin. Matematik. Forene. Comput. 40, 41-63, 2002.