Hrabě Pappa

hrabě Pappa

Pojmenoval podle	Pappus z Alexandrie
Vrcholy	osmnáct
žebra	27
Poloměr	čtyři
Průměr	čtyři
obvod	6
Automorfismy	216
Chromatické číslo	2
Chromatický index	3
Vlastnosti	bipartitní symetrický kubický Hamiltonův vzdálenostně tranzitivní vzdálenost-pravidelný
Mediální soubory na Wikimedia Commons

V teorii grafů je Pappusův graf bipartitní 3 - pravidelný neorientovaný graf s 18 vrcholy a 27 hranami, což je Leviho graf Pappusovy konfigurace [1] . Je pojmenován po Pappusovi z Alexandrie , starověkém řeckém matematikovi , který věřil, že dokázal "šestiúhelníkový teorém", ve kterém Pappus popsal konfiguraci. Všechny kubické vzdálenosti-regulární grafy jsou známy. Hrabě Pappa je jedním ze třinácti takových hrabat [2] .

Počet přímočarých křížení Pappusova grafu je 5 a tento graf je nejmenší kubický graf s tímto počtem křížení (sekvence A110507 v OEIS ). Graf má obvod 6, průměr 4, poloměr 4, chromatické číslo 2, chromatický index 3 a je spojen se 3 vrcholy i se 3 okraji .

Chromatický polynom Pappusova grafu je . $(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)$

Název „Pappův graf“ se také používá pro blízký graf s devíti vrcholy [3] , jeden vrchol pro každý bod konfigurace Pappus, s hranami pro každou dvojici bodů, které jsou na stejné přímce. Tento graf je 6-pravidelný a je doplňkem spojení tří nesouvisejících trojúhelníkových grafů . První Pappusův graf lze vložit do torusu, čímž se získá pravidelná mapa s devíti šestiúhelníkovými plochami. Druhý graf tvoří s tímto vložením pravidelnou mapu s 18 trojúhelníkovými plochami.

Algebraické vlastnosti

Grupa automorfismu Pappusova grafu je grupa s řádem 216. Působí tranzitivně na vrcholy a hrany grafu. Pappusův graf je tedy symetrický . Má automorfismy, které mapují jakýkoli vrchol na jakýkoli jiný a jakoukoli hranu na jakoukoli jinou hranu. Ve Fosterově seznamu je Papův graf označen F018A a je to jediný kubický symetrický graf s 18 vrcholy [4] [5] .

Charakteristický polynom Pappusova grafu je . Toto je jediný graf s takto charakteristickým polynomem, takže v tomto případě je graf definován svým spektrem. ${\displaystyle (x-3)x^{4}(x+3)(x^{2}-3)^{6))$

Galerie

Graf Pappa, barevný pro zvýraznění různých cyklů.
chromatický index Pappusova grafu je 3.
Barevné číslo hraběte Pappus je 2.

Poznámky

↑ Weisstein, Eric W. Pappus Graph na webu Wolfram MathWorld .
↑ Brouwer, AE; Cohen, A. M.; a Neumaier, A. Distance—Regular Graphs. New York: Springer-Verlag, 1989.
↑ V Kagno. Desarguesovy a Pappusovy grafy a jejich grupy. — American Journal of Mathematics. - The Johns Hopkins University Press, 1947. - V. 69. - S. 859-863. - doi : 10.2307/2371806 .
↑ Royle, G. "Krychlové symetrické grafy (The Foster Census)." Archivováno z originálu 20. července 2008.
↑ Conder, M. a Dobcsányi, P. "Trivalentní symetrické grafy až do 768 vrcholů." J. Combin. Matematika. Kombajn. Počítat. 40, 41-63, 2002.