Hranolový graf

V teorii grafů je hranolový graf graf , který má jeden z hranolů jako kostru.

Příklady

Jednotlivé grafy lze pojmenovat podle přidružených těles:


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)

Přestože geometricky hvězdicové polygony slouží také jako plochy další sekvence (samoprotínajících se a nekonvexních) hranolových polytopů, grafy těchto hvězdicových hranolů jsou izomorfní s hranolovými grafy a netvoří samostatnou sekvenci grafů.

Konstrukce

Hranolové grafy jsou příklady zobecněných Petersenových grafů s parametry GP( n ,1). Grafy lze tvořit i jako přímý součin cyklu a jednotkové hrany [1] .

Jako mnoho vertex-tranzitivních grafů, prizmatické grafy mohou být konstruovány jako Cayleyovy grafy . Dihedrální grupa řádu n je grupa symetrie pravidelného n -úhelníku v rovině. Na n - úhelník působí rotacemi a odrazy. Skupinu lze generovat dvěma prvky, rotací o úhel a jedním odrazem, a Cayleyův graf této skupiny s touto generující množinou je hranolový graf. Abstraktně, skupina má úlohu (kde r je rotace a f je odraz) a Cayleyův graf má r a f (nebo r , r −1 a f ) jako generátory [1]

Graf n - gonálního hranolu s lichým n lze sestrojit jako cirkulační graf , ale tato konstrukce nefunguje pro sudé hodnoty n [1] .

Vlastnosti

Graf n -gonálního hranolu má 2n vrcholů a 3n hran. Grafy jsou pravidelné kubické grafy . Protože hranol má symetrie, které přenášejí jakýkoli vrchol do kteréhokoli jiného, ​​hranolové grafy jsou vertex-tranzitivní grafy . Jelikož se jedná o polyedrické grafy , jsou tyto grafy také rovinnými grafy spojenými s vrcholem 3 . Libovolný hranolový graf má Hamiltonovský cyklus [2] .

Ze všech dvojitě souvislých kubických grafů mají hranolové grafy až do konstantního faktoru největší možný počet 1-rozkladů grafu . 1-rozklad je rozdělení okraje grafu na tři dokonalé shody, nebo ekvivalentně tříbarevné obarvení okraje grafu. Libovolný bi-spojený kubický graf s n vrcholy má O (2 n /2 ) 1-rozkladů a hranolový graf má Ω (2 n /2 ) 1-rozkladů [3] .

Počet kostrů grafu n -gonálního hranolu je dán vzorcem [4] .

Pro n = 3, 4, 5, ... se tato čísla rovnají

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

Grafy n -gonálních hranolů pro sudé n jsou částečné krychle . Tvoří jednu z mála známých nekonečných rodin grafů kubických parciálních krychlí a jsou to (až na čtyři výjimky) jediné vertex-tranzitivní kubické parciální krychle [5] .

Graf pětiúhelníkového hranolu je jedním ze zakázaných menších pro grafy se šířkou stromu tři [6] . Grafy trojúhelníkového hranolu a krychle mají šířku stromu přesně tři, ale všechny větší hranoly mají šířku stromu čtyři.

Související grafy

Další nekonečné rodiny polyhedrálních grafů podobně založených na mnohostěnech s pravidelnou základnou zahrnují antihranolové grafy a kola pyramidové grafy ). Jiné vertex-tranzitivní polyedrální grafy jsou Archimedovy grafy .

Pokud se dva cykly prizmatického grafu přeruší odstraněním jedné hrany na stejném místě v obou cyklech, dostaneme žebřík . Pokud jsou dvě odstraněné hrany nahrazeny dvěma křížícími se hranami, dostaneme nerovinný graf " Möbiův žebřík " [7] .

Poznámky

  1. ↑ 1 2 3 Weisstein, Eric W. Prism graph  (anglicky) na webu Wolfram MathWorld .
  2. ↑ Read, Wilson, 2004 , str. 261, 270.
  3. ↑ Eppstein, 2013 . Eppstein připisuje pozorování, že hranolové grafy mají téměř maximální počet 1-rozkladů, Gregu Kuperbergovi , který toto pozorování provedl soukromě.
  4. ↑ Jagers, 1988 , str. 151–154.
  5. ↑ Mark, 2015 .
  6. ↑ Arnborg, Proskurowski, Corneil, 1990 , str. 1–19.
  7. ↑ Guy, Harary, 1967 , str. 493–496.

Literatura