Prisme graf

I grafteori er en prismegraf en graf , der har et af prismerne som skelet.

Eksempler

Individuelle grafer kan navngives efter de tilknyttede organer:


Y 3 = GP(3,1)
Y 4 \ u003d Q 3 \u003d GP (4,1)
Y 5 = GP(5,1)
Y 6 = GP(6,1)
Y 7 = GP(7,1)
Y8 = GP (8,1)

Selvom geometrisk stjerneformede polygoner også tjener som flader af en anden sekvens af (selvskærende og ikke-konvekse) prismatiske polytoper, er graferne for disse stjerneformede prismer isomorfe i forhold til prismegraferne og danner ikke en separat sekvens af grafer.

Konstruktion

Prismegrafer er eksempler på generaliserede Petersen-grafer med parametrene GP( n ,1). Grafer kan også dannes som et direkte produkt af en cyklus og en enhedskant [1] .

Som mange vertex-transitive grafer kan prismatiske grafer konstrueres som Cayley-grafer . Den dihedrale gruppe af orden n er symmetrigruppen af ​​en regulær n -gon i planet. Det virker på n - gon ved rotationer og refleksioner. En gruppe kan genereres af to elementer, en rotation med en vinkel og en refleksion, og Cayley-grafen for denne gruppe med dette generatorsæt er en prismegraf. Abstrakt har gruppen en opgave (hvor r er en rotation og f er en refleksion), og Cayley-grafen har r og f (eller r , r −1 og f ) som generatorer [1]

Grafen for et n -gonalt prisme med ulige n kan konstrueres som en cirkulerende graf , men denne konstruktion virker ikke for lige værdier af n [1] .

Egenskaber

Grafen for et n -gonalt prisme har 2n hjørner og 3n kanter. Graferne er almindelige kubiske grafer . Fordi et prisme har symmetrier, der tager et hvilket som helst toppunkt til et hvilket som helst andet, er prismegrafer toppunkttransitive grafer . Da de er polyedriske grafer , er disse grafer også vertex-3-forbundne plane grafer . Enhver prismegraf har en Hamiltonsk cyklus [2] .

Blandt alle dobbeltforbundne kubiske grafer har prismegrafer, op til en konstant faktor, det størst mulige antal 1-nedbrydninger af grafen . En 1-dekomponering er en opdeling af grafens kant sat i tre perfekte matchninger, eller tilsvarende en trefarvet kantfarvning af grafen. Enhver bi-forbundet kubisk graf med n toppunkter har O (2 n /2 ) 1-nedbrydninger, og en prismegraf har Ω (2 n /2 ) 1-nedbrydninger [3] .

Antallet af spændende træer i grafen for et n -gonalt prisme er givet ved formlen [4] .

For n = 3, 4, 5, ... er disse tal ens

78, 388, 1810, 8106, 35294, ...

Grafer af n -gonale prismer for lige n er partielle terninger . De danner en af ​​de få kendte uendelige familier af kubiske partielle terninger, og de er (med fire undtagelser) de eneste vertex-transitive kubiske partielle terninger [5] .

Den femkantede prismegraf er en af ​​de forbudte mindre for grafer med træbredde tre [6] . De trekantede prisme- og kubegrafer har træbredde præcis tre, men alle større prismer har træbredde fire.

Relaterede grafer

Andre uendelige familier af polyedriske grafer, der på samme måde er baseret på almindelige basispolyedre, omfatter antiprismegrafer og hjul ( ) . Andre toppunkt-transitive polyhedriske grafer er de arkimedeiske grafer .

Hvis to cyklusser af en prismatisk graf brydes ved at fjerne en kant på samme sted i begge cyklusser, får vi en stige . Hvis to fjernede kanter erstattes af to krydsende kanter, får vi en ikke-plan graf " Möbius ladder " [7] .

Noter

  1. ↑ 1 2 3 Weisstein, Eric W. Prism-graf  (engelsk) på Wolfram MathWorld- webstedet .
  2. ↑ Læs, Wilson, 2004 , s. 261, 270.
  3. ↑ Eppstein, 2013 . Eppstein tilskriver observationen, at prismegrafer har et næsten maksimalt antal 1-nedbrydninger, til Greg Kuperberg , som foretog denne observation privat.
  4. ↑ Jagers, 1988 , s. 151-154.
  5. ↑ Mark, 2015 .
  6. ↑ Arnborg, Proskurowski, Corneil, 1990 , s. 1-19.
  7. ↑ Guy, Harary, 1967 , s. 493-496.

Litteratur