Létragráf
Sablon:Gráf infobox 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.[1]
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.[2][3]
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 .
-
A létragráf kromatikus száma 2.
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ő.[4]
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:
 CL3 |
 CL4 |
 CL5 |
 CL6 |
 CL7 |
 CL8 |
Möbius-létragráf
Sablon: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
- ↑ Sablon:MathWorld
- ↑ 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.
- ↑ Sablon:Cite journal