Köşe geçişliliği ve kenar değiştirme özelliği

Aug 18 2020

Basit, yönsüz bir grafik $G=(V,E)$varsa köşe-geçişli olduğu söyleniyor$a,b\in V$ bir grafik izomorfizmi var $\varphi:V\to V$ öyle ki $\varphi(a) = b$.

Bir grafik diyoruz $G=(V,E)$herhangi bir kenar için kenar değiştirme özelliğine sahiptir$e = \{x,y\} \in E$ bir grafik izomorfizmi var $\varphi:V\to V$ öyle ki $\varphi(x) = y$ ve $\varphi(y) = x$.

Bu özelliklerden herhangi biri, bağlantılı grafikler için diğerini ifade ediyor mu?

Yanıtlar

2 DánielG. Aug 20 2020 at 00:36

Ekin'in yorumlarda söylediği gibi, bağlantılı grafikler için kenar değiştirme özelliği, bir yol boyunca kenar değişimlerini oluşturarak köşe geçişini ifade eder.

Diğer ima doğru değil. Herhangi bir bitişik köşe çifti için bir grafik simetriktir$(u_1,v_1)$ ve $(u_2,v_2)$ bir otomorfizm gönderimi var $u_1$ -e $u_2$ ve $v_1$ -e $v_2$. Bunun kenar geçişinden daha güçlü olduğuna dikkat edin, çünkü kenar haritasının uç noktalarının diğer kenarın uç noktalarına olan şeklini belirleyebiliriz (bu nedenle, böyle bir grafiğe yay geçişli de denir ).

Şimdi Wikipedia , tepe geçişli ve kenar geçişli ancak simetrik olmayan grafikler olduğunu iddia ediyor . Böyle bir grafik, kenar değiştirme özelliğine sahip olamaz, aksi takdirde herhangi bir bitişik köşe çiftini, kenar geçişini kullanarak ve ardından gerekirse kenarı değiştirerek başka bir bitişik köşe çiftine gönderebiliriz.

Köşe geçişliliği, kenar geçişliliği ve kenar değiştirme özelliği arasındaki bağlantıyla ilgili olarak: üçgen prizma grafiği , kenar değiştirme özelliğine sahiptir ve bu nedenle tepe geçişlidir, ancak kenar geçişli değildir. Köşe geçişli ancak kenar geçişli olmayan ve kenar değiştirme özelliği kafamın tepesinde olmayan bir grafik düşünemiyorum, ancak böyle grafikler olmasaydı şaşırırdım.