Merdiven grafiği - Ladder graph

Merdiven grafiği
Merdiven grafiği L8.svg
Merdiven grafiği L8.
Tepe noktaları2n
Kenarlar3n-2
Kromatik numara2
Kromatik dizin3 için n> 2
2 için n = 2
1 için n = 1
ÖzellikleriBirim mesafesi
Hamiltoniyen
Düzlemsel
Bipartit
GösterimLn
Grafikler ve parametreler tablosu

İçinde matematiksel alanı grafik teorisi, merdiven grafiği Ln bir düzlemsel yönsüz grafik ile 2n köşeler ve 3n-2 kenarlar.[1]

Merdiven grafiği şu şekilde elde edilebilir: Kartezyen ürün iki yol grafikleri, birinin yalnızca bir kenarı vardır: Ln,1 = Pn × P2.[2][3]

Özellikleri

Yapım gereği, merdiven grafiği Ln izomorfiktir ızgara grafiği G2,n ve bir merdivene benziyor n basamaklar. Bu Hamiltoniyen çevresi 4 ile (eğer n> 1) ve kromatik indeks 3 (eğer n> 2).

kromatik sayı merdiven grafiğinin% 2'si ve kromatik polinom dır-dir .

Merdiven grafikleri L1, L2, L3, L4 ve L5.

Merdiven basamak grafiği

Bazen "merdiven grafiği" terimi, n × P2 merdiven basamak grafiği, grafik birliği olan n yol grafiğinin kopyaları P2.

Merdiven basamaklı grafikler LR1, LR2, LR3, LR4, ve LR5.

Dairesel merdiven grafiği

Ana makale: Prizma grafiği

dairesel merdiven grafiği CLn dört 2 derecelik köşeyi bir Düz bir şekilde veya bir uzunluk döngüsünün Kartezyen çarpımı ile n≥3 ve bir kenar.[4]Sembollerde, CLn = Cn × P2. Var 2n düğümler ve 3n Merdiven grafiği gibi, bağlı, düzlemsel ve Hamiltoniyen, ama bu iki parçalı ancak ve ancak n eşittir.

Dairesel merdiven grafiği, çok yüzlü grafikler prizmalar, bu nedenle daha yaygın olarak adlandırılırlar prizma grafikleri.

Dairesel merdiven grafikleri:

Üçgen prizmatik graph.png
CL3		Cubical graph.png
CL4		Beşgen prizmatik graph.png
CL5		Altıgen prizmatik graph.png
CL6		Heptagonal prizmatik graph.png
CL7		Sekizgen prizmatik graph.png
CL8

Möbius merdiveni

Ana makale: Möbius merdiveni

Dört 2 derecelik köşeyi birbirine bağlama çapraz oluşturur kübik grafik Möbius merdiveni denir.

Möbius merdiveninin iki görünümü M16 .

Referanslar

  1. ^ Weisstein, Eric W. "Merdiven Grafiği". MathWorld.
  2. ^ Hosoya, H. ve Harary, F. "Üç Çit Grafiğinin Eşleşen Özellikleri Üzerine." J. Math. Chem. 12, 211-218, 1993.
  3. ^ Noy, M. ve Ribó, A. "Yinelemeli Olarak Yapılandırılabilir Grafik Aileleri." Adv. Appl. Matematik. 32, 350-363, 2004.
  4. ^ Chen, Yichao; Gross, Jonathan L .; Mansour, Toufik (Eylül 2013). "Dairesel Merdivenlerin Toplam Gömme Dağılımları". Journal of Graph Theory. 74 (1): 32–57. CiteSeerX  10.1.1.297.2183. doi:10.1002 / jgt.21690.