Köşe geçişli grafik - Vertex-transitive graph

Otomorfizmlerine göre tanımlanan grafik aileleri
mesafe geçişli → düzenli mesafe ← kesinlikle düzenli
↓
simetrik (ark geçişli) ← t -geçişmeli, t  ≥ 2 çarpık simetrik
↓
(bağlıysa)
köşe ve kenar geçişli 		→ kenar geçişli ve düzenli → kenar geçişli
↓ ↓ ↓
köşe geçişli → düzenli → (iki taraflı ise)
biregüler
↑
Cayley grafiği ← sıfır simetrik asimetrik

Olarak matematiksel alanında grafik teorisi , bir tepe-geçişli grafik a, grafik G herhangi iki köşe verilen içinde, v 1 ve v 2 arasında G , bazı vardır otomorfizm

öyle ki

Başka bir deyişle, bir grafik, eğer otomorfizm grubu kendi köşelerinde geçişli olarak hareket ediyorsa, tepe geçişlidir . Grup eylemleri aynı olduğundan , bir grafik ancak ve ancak grafik tamamlayıcısı ise tepe geçişlidir .

İzole köşeleri olmayan her simetrik grafik köşe geçişlidir ve her köşe geçişli grafik normaldir . Bununla birlikte, tüm köşe geçişli grafikler simetrik değildir (örneğin, kesilmiş tetrahedronun kenarları ) ve tüm normal grafikler köşe geçişli değildir (örneğin, Frucht grafiği ve Tietze'nin grafiği ).

Sonlu örnekler

Kesik tetrahedronun kenarları, simetrik olmayan bir tepe-geçişli grafik (ayrıca bir Cayley grafiği ) oluşturur .

Sonlu köşe geçişli grafikler, simetrik grafikleri ( Petersen grafiği , Heawood grafiği ve Platonik katıların köşeleri ve kenarları gibi ) içerir. Sonlu Cayley grafikleri ( küp bağlantılı döngüler gibi ), Arşimet katılarının köşeleri ve kenarları gibi tepe geçişlidir (bunlardan sadece ikisi simetriktir). Potočnik, Spiga ve Verret en fazla 1280 köşede birbirine bağlı tüm kübik köşe geçişli grafiklerin bir sayımını oluşturdu.

Her Cayley grafiği köşe geçişli olsa da, Cayley grafikleri olmayan başka köşe geçişli grafikler de vardır. En ünlü örneği Petersen grafiktir, fakat diğerleri de dahil olmak üzere inşa edilebilir çizgi grafiğidir ait kenar geçişli olmayan iki parçalı olan grafikler tek tepe derece.

Özellikleri

Kenar bağlantısı , bir tepe-geçişli grafik eşittir derecesi d ise, tepe-bağlantı en az 2 (olacaktır d  + 1) / 3. Derece 4 veya daha düşükse veya grafik de kenar geçişli ise veya grafik minimum Cayley grafiğiyse , köşe bağlantısı da d'ye eşit olacaktır .

Sonsuz örnekler

Sonsuz köşe geçişli grafikler şunları içerir:

Mesafe fonksiyonlarının oranı aşağıdan ve yukarıdan sınırlandırılmışsa, iki sayılabilir köşe geçişli grafiğe yarı izometrik denir . İyi bilinen bir varsayım , her sonsuz köşe geçişli grafiğin bir Cayley grafiğine yarı izometrik olduğunu belirtti . 2001'de Diestel ve Leader tarafından bir karşı örnek önerildi . 2005'te Eskin, Fisher ve Whyte karşı örneği doğruladılar.

Ayrıca bakınız

Referanslar

  1. ^ a b Godsil, Chris ; Royle, Gordon (2013) [2001], Cebirsel Grafik Teorisi , Matematikte Lisansüstü Metinleri , 207 , Springer, ISBN   978-1-4613-0163-9 CS1 Maint: önerilmeyen parametre ( bağlantı ) .
  2. ^ Potočnik P., Spiga P. & Verret G. (2013), "1280 köşeye kadar kübik tepe geçişli grafikler", Sembolik Hesaplama Dergisi , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016 / j. jsc.2012.09.002 , S2CID   26705221 .
  3. ^ Lauri, Josef; Scapellato, Raffaele (2003), Grafik otomorfizmlerinde ve yeniden yapılandırmada konular , Londra Matematik Derneği Öğrenci Metinleri, 54 , Cambridge University Press, s. 44, ISBN   0-521-82151-7 , MR   1971819 . Lauri ve Scapelleto bu yapıyı Mark Watkins'e emanet ediyor.
  4. ^ Babai, L. (1996), Technical Report TR-94-10 , University of Chicago, 2010-06-11 tarihinde orjinalinden arşivlendi
  5. ^ Diestel, Reinhard; Leader, Imre (2001), "Cayley dışı grafiklerin sınırına ilişkin bir varsayım" (PDF) , Journal of Algebraic Combinatorics , 14 (1): 17–25, doi : 10.1023 / A: 1011257718029 , S2CID   10927964 CS1 Maint: önerilmeyen parametre ( bağlantı ) .
  6. ^ Eskin, Alex; Fisher, David; Whyte Kevin (2005). "Yarı-izometriler ve çözülebilir grupların sertliği". arXiv : math.GR/0511647 . .

Dış bağlantılar