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 .
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.
Trappens kromatiske tal er 2.