Prizma gráf

A gráfelméletben a prizmagráf olyan gráf , amelynek az egyik prizma váza.

Példák

Az egyes gráfok a kapcsolódó testek szerint nevezhetők el:


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

Bár a geometriailag csillagozott sokszögek egy másik (önmetsző és nem konvex) prizmatikus politóp sorozat lapjaiként is szolgálnak, ezeknek a csillagozott prizmáknak a gráfjai izomorfak a prizmagráfokkal, és nem képeznek külön gráfsorozatot.

Épület

A prizmagráfok a GP( n ,1) paraméterekkel rendelkező általánosított Petersen-gráfok példái . A grafikonok egy ciklus és egy egységél közvetlen szorzataként is kialakíthatók [1] .

Mint sok csúcstranzitív gráf, a prizmatikus gráfok is Cayley -gráfokként szerkeszthetők . Az n rendű diédercsoport egy szabályos n -gon szimmetriacsoportja a síkban. Forgással és visszaverődéssel hat az n - gonra. Egy csoportot két elem, egy szöggel történő elforgatás és egy visszaverődés generálhat, és ennek a csoportnak a Cayley-gráfja ezzel a generáló halmazzal egy prizmagráf. Absztrakt módon a csoportnak van egy feladata (ahol r egy forgás és f egy tükrözés), a Cayley-gráfban pedig r és f (vagy r , r −1 és f ) generátorok [1]

Egy n -szögű prizma páratlan n -jű gráfja megszerkeszthető körgráfként , de ez a konstrukció nem működik n páros értékeire [1] .

Tulajdonságok

Egy n -szögű prizma gráfjának 2n csúcsa és 3n éle van. A grafikonok szabályos köbös grafikonok . Mivel a prizmának vannak olyan szimmetriái, amelyek bármely csúcsot bármely másik csúcshoz elviszik, a prizmagráfok csúcstranzitív gráfok . Poliéder gráfok lévén ezek a gráfok egyben csúcs-3-mal összefüggő síkgráfok is . Bármely prizmagráfnak van Hamilton-ciklusa [2] .

A duplán összefüggő köbös gráfok közül a prizmagráfokon van egy állandó tényezőig a lehető legnagyobb számú gráf 1-es dekompozíciója . Az 1-es dekompozíció a gráf élének három tökéletes illeszkedésre halmozott felosztása, vagy ennek megfelelően a gráf háromszínű élszínezése . Bármely n csúcsú , kettõs összeköttetésû köbös gráfnak O (2 n /2 ) 1-felbontása van, a prizmagráfnak pedig Ω (2 n /2 ) 1-felbontása van [3] .

Egy n -szögű prizma gráfjának feszítőfáinak számát a [4] képlet adja meg .

Ha n = 3, 4, 5, ... ezek a számok egyenlőek

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

A páros n szögű prizmák grafikonjai részkockák . A néhány ismert végtelen köbös parciális kocka gráfok egyikét alkotják , és (négy kivétellel) az egyetlen csúcstranzitív köbös parciális kockák [5] .

Az ötszögű prizmagráf a három faszélességű gráfok egyik tiltott melléke [6] . A háromszög alakú prizma és kocka gráfok faszélessége pontosan három, de minden nagyobb prizma négyes faszélességű.

Kapcsolódó grafikonok

A poliéder gráfok más végtelen családjai, amelyek hasonlóan a szabályos alappoliédereken alapulnak, magukban foglalják az antiprizmagráfokat és a kerekeket piramisgráfok ). Más csúcstranzitív poliéder gráfok az arkhimédeszi gráfok .

Ha egy prizmatikus gráf két ciklusát úgy törjük meg, hogy mindkét ciklusban egy élt eltávolítunk, akkor egy létrát kapunk . Ha két eltávolított élt két keresztező élre cserélünk, egy nem síkbeli gráfot kapunk " Möbius létra " [7] .

Jegyzetek

  1. ↑ 1 2 3 Weisstein, Eric W. Prism graph  (angol) a Wolfram MathWorld weboldalán .
  2. ↑ Olvasás, Wilson, 2004 , p. 261, 270.
  3. ↑ Eppstein, 2013 . Eppstein Greg Kuperbergnek tulajdonítja azt a megfigyelést, miszerint a prizmagráfok majdnem maximális számú 1-es dekompozíciót tartalmaznak , aki ezt a megfigyelést privátban tette.
  4. ↑ Jagers, 1988 , p. 151–154.
  5. ↑ Mark, 2015 .
  6. ↑ Arnborg, Proskurowski, Corneil, 1990 , p. 1–19.
  7. ↑ Guy, Harary, 1967 , p. 493–496.

Irodalom