Stige (grafteori)

Earl "Ladder"
Toppe 2n
ribben n+2(n-1)
Kromatisk tal 2
Kromatisk indeks 3 for n>2
2 for n=2
1 for n=1
Ejendomme
Hamiltonsk enhedsafstandsgraf
plan
todelt
Betegnelse L n
 Mediefiler på Wikimedia Commons

I grafteori er en stige L n en plan urettet graf med 2n spidser og n+2(n-1) kanter [1] .

Stigen kan fås som et direkte produkt af to baner , hvoraf den ene kun har én kant - L n = P n × P 1 [2] [3] . Hvis vi tilføjer yderligere to skærende kanter, der forbinder de fire hjørner af en stige med grad to, får vi en kubisk graf - Möbius-stigen .

Ved konstruktion er stigen L n isomorf i forhold til gitteret G 2, n og ligner en stige med n trin. Grafen er Hamiltonsk med omkreds 4 (hvis n>1 ) og kromatisk indeks 3 (hvis n>2 ).

Det kromatiske tal på stigen er 2, og dets kromatiske polynomium er .

Ringstigegraf

Ringstigegrafen CL n er det direkte produkt af en cyklus med længden n≥3 og en kant [4] . På symbolsk form CL n = C n × P 1 . Grafen har 2n hjørner og 3n kanter. Ligesom stiger er en graf forbundet , plan , og Hamiltonian , men en graf er todelt , hvis og kun hvis n er lige.

Galleri

Noter

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

Litteratur