Kreivi Pappa

Kreivi Pappa

Nimetty	Pappus Aleksandriasta
Huiput	kahdeksantoista
kylkiluut	27
Säde	neljä
Halkaisija	neljä
Ympärysmitta	6
Automorfismit	216
Kromaattinen numero	2
Kromaattinen indeksi	3
Ominaisuudet	bipartite symmetric cubic Hamiltonin etäisyystransitiivinen etäisyys-säännöllinen
Mediatiedostot Wikimedia Commonsissa

Graafiteoriassa Pappus-graafi on kaksiosainen 3 - säännöllinen suuntaamaton graafi, jossa on 18 kärkeä ja 27 reunaa, joka on Pappus-konfiguraation Levi-graafi [1] . Se on nimetty Pappuksen Aleksandrialaisen mukaan, muinaisen kreikkalaisen matemaatikon mukaan, joka uskoi todistaneensa "kuusikulmiolauseen", jossa Pappus kuvaili konfiguraatiota. Kaikki kuutioetäisyys -säännölliset kuvaajat tunnetaan. Kreivi Pappa on yksi kolmestatoista sellaisesta kreivistä [2] .

Pappus-graafin suoraviivaisten risteysten määrä on 5, ja tämä kuvaaja on pienin kuutiograafi, jolla on risteyksiä (sekvenssi A110507 OEIS : ssä ). Graafilla on ympärysmitta 6, halkaisija 4, säde 4, kromaattinen luku 2, kromaattinen indeksi 3, ja se on yhdistetty sekä 3 kärkeen että 3 reunaan .

Pappus-graafin kromaattinen polynomi on . ${\näyttötyyli (x-1)x(x^{16}-26x^{15}+325x^{14}-2600x^{13}+14950x^{12}-65762x^{11}+}$ $229852x^{10}-653966x^{9}+1537363x^{8}-3008720x^{7}+4904386x^{6}-$ $6609926x^{5}+7238770x^{4}-6236975x^{3}+3989074x^{2}-1690406x+356509)$

Nimeä "Pappa-graafi" käytetään myös läheiselle graafille, jossa on yhdeksän kärkeä [3] , yksi piste jokaiselle Pappus-konfiguraation pisteelle, ja kullekin samalla viivalla olevalle pisteparille on reunat. Tämä kaavio on 6-säännöllinen ja täydentää kolmen toisiinsa liittymättömän kolmiokaavion liitosta . Ensimmäinen Pappus-graafi voidaan upottaa torukseen, jolloin saadaan säännöllinen kartta , jossa on yhdeksän kuusikulmaista pintaa. Toinen kuvaaja muodostaa tämän upotuksen avulla säännöllisen kartan, jossa on 18 kolmion muotoista pintaa.

Algebralliset ominaisuudet

Pappus-graafin automorfismiryhmä on ryhmä, jonka kertaluku on 216. Se vaikuttaa transitiivisesti graafin kärkipisteisiin ja reunoihin. Siten Pappus-graafi on symmetrinen . Siinä on automorfismit, jotka kuvaavat minkä tahansa kärjen mihin tahansa toiseen ja minkä tahansa reunan mihin tahansa muuhun reunaan. Fosterin luettelossa Papan graafi on merkitty F018A ja se on ainoa kuutiosymmetrinen graafi, jossa on 18 kärkeä [4] [5] .

Pappus-graafin ominaispolynomi on . Tämä on ainoa graafi, jolla on tällainen ominaispolynomi, joten tässä tapauksessa graafi määritellään sen spektrin mukaan. ${\näyttötyyli (x-3)x^{4}(x+3)(x^{2}-3)^{6))$

Galleria

Pappa-kaavio, värillinen korostamaan eri jaksoja.
Pappus-graafin kromaattinen indeksi on 3.
Kreivi Pappusin kromaattinen luku on 2.

Muistiinpanot

↑ Weisstein, Eric W. Pappus Graph Wolfram MathWorld -verkkosivustolla .
↑ Brouwer, AE; Cohen, A. M.; ja Neumaier, A. Etäisyys—säännölliset kaaviot. New York: Springer-Verlag, 1989.
↑ Kagnossa. Desarguesin ja Pappuksen graafit ja niiden ryhmät. - American Journal of Mathematics. - The Johns Hopkins University Press, 1947. - V. 69. - S. 859-863. - doi : 10.2307/2371806 .
↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arkistoitu alkuperäisestä 20. heinäkuuta 2008.
↑ Conder, M. ja Dobcsányi, P. "Trivalent Symmetric Graphs Jopa 768 Vertices." J. Combin. Matematiikka. Yhdistää. Comput. 40, 41-63, 2002.