A matematika, azon belül a gráfelmélet területén az Ln-nel jelölt létragráf (ladder graph) egy 2n csúccsal és 3n−2 éllel rendelkező összefüggő, irányítatlan, síkbarajzolható gráf.
A létragráf előállítható két útgráf Descartes-szorzataként, amennyiben az egyik útgráf csak egyetlen éllel rendelkezik: Ln,1 = Pn × P2.Hosoya, H. and Harary, F. "On the Matching Properties of Three Fence Graphs." J. Math. Chem. 12, 211-218, 1993.Noy, M. and Ribó, A. "Recursively Constructible Families of Graphs." Adv. Appl. Math. 32, 350-363, 2004.
Tulajdonságok A konstrukciós szabály alapján nyilvánvaló, hogy az Ln létragráf a G2,n rácsgráffal izomorf, és valóban emlékeztet egy n fokkal rendelkező létrára. Rendelkezik Hamilton-körrel, girthparamétere 4 (ha n>1), élkromatikus száma pedig 3 (ha n>2). A gráf négy sarki helyzetű csúcsának fokszáma 2, a többi csúcsé 3. Az Ln létragráf teljes párosításainak száma megegyezik az Fn+1 Fibonacci-számmal.
A létragráf kromatikus száma 2, kromatikus polinomja pedig .
Létrafok-gráf Néha létragráf alatt az n × P2 létrafok-gráfot (ladder rung graph) értik, azaz n db 2 hosszúságú útgráf diszjunkt unióját.
Körkörös létragráf A létragráf négy 2 fokszámú csúcsát egyenesen összekötve, avagy egy n≥3 hosszúságú kör és egy él Descartes-szorzatával a körkörös létragráf (circular ladder graph), CLn áll elő.
Szimbolikusan: CLn = Cn × P1.
A körkörös létragráf 2n csúccsal és 3n éllel rendelkező, összefüggő síkbarajzolható gráf Hamilton-körrel, de kizárólag akkor páros, ha n páros.
A körkörös létragráfok a hasábok poliédergráfjai, ezért hasábgráfnak is nevezik őket.
Körkörös létragráfok: CL3CL4CL5CL6CL7CL8
Möbius-létragráf
Egy létragráf négy 2 fokszámú csúcsát keresztben összekötve 3-reguláris gráf jön létre, amit Möbius-létrának neveznek.
Fordítás
Jegyzetek
Kategória:Parametrikus gráfcsaládok Kategória:Síkgráfok Kategória:2 kromatikus számú gráfok