Stege (grafteori)

Earl "Ladder"
Toppar 2n
revben n+2(n-1)
Kromatiskt nummer 2
Kromatiskt index 3 för n>2
2 för n=2
1 för n=1
Egenskaper
Hamiltonsk enhetsdistansdiagram
plan
tvådelad
Beteckning L n
 Mediafiler på Wikimedia Commons

I grafteorin är en stege L n en plan oriktad graf med 2n hörn och n+2(n-1) kanter [1] .

Stegen kan erhållas som en direkt produkt av två banor , varav den ena har endast en kant - L n = P n × P 1 [2] [3] . Om vi ​​lägger till ytterligare två skärande kanter som förbinder de fyra hörnen på en stege med grad två, får vi en kubisk graf - Möbius-stegen .

Genom sin konstruktion är stegen L n isomorf mot gittret G 2, n och ser ut som en stege med n steg. Grafen är Hamiltonsk med omkrets 4 (om n>1 ) och kromatiskt index 3 (om n>2 ).

Det kromatiska numret på stegen är 2 och dess kromatiska polynom är .

Ringstegediagram

Ringstegegrafen CL n är den direkta produkten av en cykel med längden n≥3 och en kant [4] . I symbolisk form CL n = C n × P 1 . Grafen har 2n hörn och 3n kanter. Liksom stegar är en graf ansluten , plan och Hamiltonian , men en graf är tvådelad om och bara om n är jämnt.

Galleri

Anteckningar

  1. ↑ Weisstein, Eric W. Ladder Graph  på Wolfram MathWorld- webbplatsen .
  2. ↑ Hosoya, Harary, 1993 , sid. 211-218.
  3. ↑ Noy, Ribó, 2004 , sid. 350-363.
  4. ↑ Chen, Gross, Mansour, 2013 , sid. 32–57.

Litteratur