Prisma graf

Inom grafteorin är en prismagraf en graf som har ett av prismorna som ett skelett.

Exempel

Individuella grafer kan namnges enligt de tillhörande organen:


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)

Även om geometriskt stellerade polygoner också fungerar som ytor av en annan sekvens av (självkorsande och icke-konvexa) prismatiska polytoper, är graferna för dessa stelliserade prismor isomorfa till prismagraferna och bildar inte en separat sekvens av grafer.

Byggnad

Prismagrafer är exempel på generaliserade Petersengrafer med parametrarna GP( n ,1). Grafer kan också bildas som en direkt produkt av en cykel och en enhetskant [1] .

Liksom många vertextransitiva grafer kan prismatiska grafer konstrueras som Cayley-grafer . Den dihedriska gruppen av ordning n är symmetrigruppen för en regelbunden n -gon i planet. Den verkar på n - gon genom rotationer och reflektioner. En grupp kan genereras av två element, en rotation med en vinkel och en reflektion, och Cayley-grafen för denna grupp med denna generatoruppsättning är en prismagraf. Sammanfattningsvis har gruppen en uppgift (där r är en rotation och f är en reflektion) och Cayley-grafen har r och f (eller r , r −1 och f ) som generatorer [1]

Grafen för ett n -gonalt prisma med udda n kan konstrueras som en cirkulationsgraf , men denna konstruktion fungerar inte för jämna värden på n [1] .

Egenskaper

Grafen för ett n -gonalt prisma har 2n hörn och 3n kanter. Graferna är vanliga kubikgrafer . Eftersom ett prisma har symmetrier som tar vilken vertex som helst till vilken som helst, är prismagrafer vertextransitiva grafer . Eftersom de är polyedriska grafer , är dessa grafer också vertex-3-kopplade plana grafer . Varje prismagraf har en Hamiltonsk cykel [2] .

Bland alla dubbelkopplade kubikgrafer har prismagrafer, upp till en konstant faktor, största möjliga antal 1-uppdelningar av grafen . En 1-sönderdelning är en uppdelning av grafens kantuppsättning i tre perfekta matchningar, eller, motsvarande, en trefärgad kantfärgning av grafen. Varje dubbelkopplad kubisk graf med n hörn har O (2 n /2 ) 1-nedbrytningar, och en prismagraf har Ω (2 n /2 ) 1-sönderdelningar [3] .

Antalet spännande träd i grafen för ett n -gonalt prisma ges av formeln [4] .

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

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

Grafer av n -gonala prismor för jämna n är partiella kuber . De bildar en av de få kända oändliga familjerna av kubiska partiella kubgrafer, och de är (med fyra undantag) de enda vertextransitiva kubiska partiella kuberna [5] .

Den femkantiga prismagrafen är en av de förbjudna minorerna för grafer med trädbredd tre [6] . De triangulära prisma- och kubgraferna har trädbredd exakt tre, men alla större prismor har trädbredd fyra.

Relaterade grafer

Andra oändliga familjer av polyedriska grafer på liknande sätt baserade på vanliga baspolyedrar inkluderar antiprismagrafer och hjul pyramidgrafer ). Andra vertextransitiva polyedriska grafer är de arkimedeiska graferna .

Om två cykler av en prismatisk graf bryts genom att ta bort en kant på samma plats i båda cyklerna får vi en stege . Om två borttagna kanter ersätts av två korsande kanter får vi en icke-plan graf " Möbiusstege " [7] .

Anteckningar

  1. ↑ 1 2 3 Weisstein, Eric W. Prismgraf  (engelska) på Wolfram MathWorld- webbplatsen .
  2. ↑ Läs, Wilson, 2004 , sid. 261, 270.
  3. ↑ Eppstein, 2013 . Eppstein tillskriver observationen att prismagrafer har ett nästan maximalt antal 1-nedbrytningar till Greg Kuperberg , som gjorde denna observation privat.
  4. ↑ Jagers, 1988 , sid. 151–154.
  5. ↑ Mark, 2015 .
  6. ↑ Arnborg, Proskurowski, Corneil, 1990 , sid. 1–19.
  7. ↑ Guy, Harary, 1967 , sid. 493–496.

Litteratur