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 .
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.