Prisma graf

Inom det matematiska området grafteorin är en prismagraf en graf som har ett av prismorna som sitt skelett.

Exempel

De individuella graferna kan vara namngivna efter den associerade soliden:

Triangulär prismagraf – 6 hörn, 9 kanter
Kubisk graf – 8 hörn, 12 kanter
Pentagonal prismagraf – 10 hörn, 15 kanter
Hexagonal prismagraf – 12 hörn, 18 kanter
Heptagonal prismagraf – 14 hörn, 21 kanter
Octagonal prisma graf – 16 hörn, 24 kanter
...

Y ₃ = GP(3,1)	Y ₄ = Q ₃ = GP(4,1)	Y ₅ = GP(5,1)	Y ₆ = GP(6,1)	Y ₇ = GP(7,1)	Y ₈ = GP(8,1)

stjärnpolygonerna geometriskt också bildar ytorna på en annan sekvens av (självkorsande och icke-konvexa) prismatiska polyedrar, är graferna för dessa stjärnprismor isomorfa till prismagraferna och bildar inte en separat sekvens av grafer.

Konstruktion

Prismagrafer är exempel på generaliserade Petersengrafer , med parametrarna GP( n ,1). De kan också konstrueras som den kartesiska produkten av en cykelgraf med en enda kant.

Som med många vertextransitiva grafer kan prismagraferna också konstrueras som Cayley-grafer . Ordnings- n dihedrisk grupp är gruppen av symmetrier för en regelbunden n -gon i planet; den verkar på n -gonen genom rotationer och reflektioner. Den kan genereras av två element, en rotation med en vinkel på 2 $π$ / n och en enda reflektion, och dess Cayley-graf med denna generator är prismagrafen. Sammanfattningsvis har gruppen presentationen ⟨ $\displaystyle \langle r,f\mid r^{n},f^{2},(rf)^ {2}\rangle }$ (där r är en rotation och f är en reflektion eller flip) och Cayley-grafen har r och f (eller r , r ⁻¹ , och f ) som sina generatorer.

De n -gonala prismagraferna med udda värden på n kan konstrueras som cirkulerande grafer $C_{2n}^{2,n}$ . Denna konstruktion fungerar dock inte för jämna värden på n .

Egenskaper

Grafen för ett n -gonalt prisma har 2 n hörn och 3 n kanter. De är regelbundna , kubiska grafer . Eftersom prismat har symmetrier som tar varje vertex till varandra vertex, är prismagraferna vertextransitiva grafer . Som polyedriska grafer är de också 3-vertex-anslutna plana grafer . Varje prismagraf har en Hamiltonsk cykel .

Bland alla dubbelkopplade kubiska grafer har prismagraferna inom en konstant faktor av största möjliga antal 1-faktoriseringar . En 1-faktorisering är en uppdelning av grafens kantuppsättning i tre perfekta matchningar, eller motsvarande en kantfärgning av grafen med tre färger. Varje dubbelkopplad n -vertex kubisk graf har O (2 ^{n /2} ) 1-faktoriseringar, och prismagraferna har Ω (2 ^{n /2} ) 1-faktoriseringar.

Antalet spännande träd i en n -gonal prismagraf ges av formeln

{\frac {n}{2}}{\bigl (}(2+{\sqrt {3}})^{ n}+(2-{\sqrt {3}})^{n}-2){\bigr .}

För n = 3, 4, 5, ... är dessa tal

75, 384, 1805, 8100, 35287, 150528, ... (sekvens A006235 i OEIS ).

De n -gonala prismagraferna för jämna värden på n är partiella kuber . De bildar en av de få kända oändliga familjerna av kubiska partiella kuber, och (förutom fyra sporadiska exempel) de enda vertextransitiva kubiska partiella kuberna.

Det femkantiga prismat är en av de förbjudna mindre för graferna för trädbredd tre. Det triangulära prisma- och kubdiagrammet har trädbredd exakt tre, men alla större prismagrafer har trädbredd fyra.

Relaterade grafer

Andra oändliga sekvenser av polyedriska grafer bildade på liknande sätt från polyedrar med baser med regelbundna polygoner inkluderar antiprismagrafer ( grafer av antiprismor ) och hjuldiagram (grafer av pyramiderna ). Andra vertex-transitiva polyedriska grafer inkluderar arkimedeiska grafer .

Om de två cyklerna i en prismagraf bryts genom att en enda kant tas bort i samma position i båda cyklerna, blir resultatet en steggraf . Om dessa två borttagna kanter ersätts av två korsade kanter blir resultatet en icke-plan graf som kallas Möbius-stege .