Vertex-transitivity dan properti edge swapping

Aug 18 2020

Grafik sederhana dan tidak berarah $G=(V,E)$dikatakan verteks-transitif jika ada$a,b\in V$ ada isomorfisme grafik $\varphi:V\to V$ seperti yang $\varphi(a) = b$.

Kami mengatakan itu grafik $G=(V,E)$memiliki properti edge-swapping jika untuk edge apa pun$e = \{x,y\} \in E$ ada isomorfisme grafik $\varphi:V\to V$ seperti yang $\varphi(x) = y$ dan $\varphi(y) = x$.

Apakah salah satu properti ini menyiratkan yang lain untuk grafik yang terhubung?

Jawaban

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

Seperti yang dikatakan Ekin dalam komentar, untuk grafik yang terhubung, properti edge-swapping menyiratkan vertex-transitivity melalui penyusunan edge swaps di sepanjang jalur.

Implikasi lainnya tidak benar. Grafik simetris jika ada pasangan simpul yang berdekatan$(u_1,v_1)$ dan $(u_2,v_2)$ ada pengiriman automorfisme $u_1$ untuk $u_2$ dan $v_1$ untuk $v_2$. Perhatikan bahwa ini lebih kuat daripada edge-transitivity, karena kita dapat menentukan cara titik akhir peta tepi ke titik ujung tepi lainnya (oleh karena itu, grafik seperti itu juga disebut transitif-busur ).

Sekarang Wikipedia menegaskan bahwa ada grafik yang verteks-transitif dan tepi-transitif tetapi tidak simetris. Grafik seperti itu tidak dapat memiliki properti edge-swapping, karena jika tidak, kita dapat mengirim pasangan simpul yang berdekatan ke pasangan lain dari simpul yang berdekatan dengan menggunakan edge-transitivity dan kemudian menukar sisi, jika diperlukan.

Mengenai hubungan antara vertex-transitivity, edge-transitivity, dan edge-swapping property: graf prisma segitiga memiliki properti edge-swapping dan karenanya merupakan vertex-transitive, tetapi bukan edge-transitive. Saya tidak dapat memikirkan grafik yang vertex-transitive tetapi tidak edge-transitive juga tidak memiliki properti edge-swapping dari atas kepala saya, meskipun saya akan terkejut jika tidak ada grafik seperti itu.