Greve Pappa

I grafteorin är en Pappus-graf en tvådelad 3 - reguljär oriktad graf med 18 hörn och 27 kanter, vilket är en Levi-graf av Pappus-konfigurationen [1] . Den är uppkallad efter Pappus av Alexandria , en forntida grekisk matematiker som trodde att han hade bevisat "hexagonsatsen" där Pappus beskrev konfigurationen. Alla kubikavstånd -reguljära grafer är kända. Greve Pappa är en av tretton sådana grevar [2] .

Antalet rätlinjiga korsningar av en Pappus-graf är 5, och denna graf är den minsta kubiska grafen med det antalet korsningar (sekvens A110507 i OEIS ). Grafen har omkrets 6, diameter 4, radie 4, kromatiskt nummer 2, kromatiskt index 3, och är både 3-vertex-ansluten och 3-kant-ansluten .

Pappus-grafens kromatiska polynom är .

Namnet "Pappa-graf" används också för en nära graf med nio hörn [3] , en vertex för varje punkt i Pappus-konfigurationen, med kanter för varje par av punkter som är på samma linje. Den här grafen är 6-regelbunden och är komplementet till föreningen av tre orelaterade triangulära grafer . Den första Pappus-grafen kan bäddas in i en torus och på så sätt få en vanlig karta med nio sexkantiga ytor. Den andra grafen bildar, med denna inbäddning, en vanlig karta med 18 triangulära ytor.

Algebraiska egenskaper

Automorfismgruppen i en Pappus-graf är en grupp med ordning 216. Den verkar transitivt på grafens hörn och kanter. Därmed är Pappus-grafen symmetrisk . Den har automorfismer som kartlägger vilken vertex som helst till vilken annan kant som helst och vilken kant som helst till vilken annan kant som helst. I Fosters lista är Papas graf märkt F018A och är den enda kubiska symmetriska grafen med 18 hörn [4] [5] .

Pappus-grafens karakteristiska polynom är . Detta är den enda grafen med ett sådant karakteristiskt polynom, så i det här fallet definieras grafen av sitt spektrum.

Galleri

• Pappa-grafen, färgad för att markera de olika cyklerna.

• det kromatiska indexet för Pappus-grafen är 3.

• Greve Pappus kromatiska tal är 2.

Anteckningar

1. ↑ Weisstein, Eric W. Pappus Graf  på Wolfram MathWorld- webbplatsen .
2. ↑ Brouwer, AE; Cohen, A.M.; och Neumaier, A. Avstånd—regelbundna grafer. New York: Springer-Verlag, 1989.
3. ↑ I Kagno. Desargues och Pappus grafer och deras 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)." Arkiverad från originalet den 20 juli 2008.
5. ↑ Conder, M. och Dobcsányi, P. "Trivalenta symmetriska grafer upp till 768 hörn." J. Combin. Matematik. Kombinera. Comput. 40, 41-63, 2002.