Vertex-transitivity และคุณสมบัติการแลกเปลี่ยนขอบ
กราฟที่เรียบง่ายและไม่บอกทิศทาง $G=(V,E)$ถูกกล่าวว่าเป็นจุดยอด - สกรรมกริยาหากมี$a,b\in V$ มีกราฟ isomorphism $\varphi:V\to V$ ดังนั้น $\varphi(a) = b$.
เราบอกว่ากราฟ $G=(V,E)$มีคุณสมบัติในการแลกเปลี่ยนขอบถ้าสำหรับขอบใด ๆ$e = \{x,y\} \in E$ มีกราฟ isomorphism $\varphi:V\to V$ ดังนั้น $\varphi(x) = y$ และ $\varphi(y) = x$.
คุณสมบัติใด ๆ เหล่านี้บ่งบอกถึงคุณสมบัติอื่น ๆ สำหรับกราฟที่เชื่อมต่อหรือไม่
คำตอบ
ดังที่ Ekin กล่าวไว้ในความคิดเห็นสำหรับกราฟที่เชื่อมต่อคุณสมบัติการแลกเปลี่ยนขอบหมายถึงจุดยอด - การขนส่งผ่านการเขียนการแลกเปลี่ยนขอบตามเส้นทาง
ความหมายอื่นไม่เป็นความจริง กราฟจะสมมาตรถ้าสำหรับคู่ของจุดยอดที่อยู่ติดกัน$(u_1,v_1)$ และ $(u_2,v_2)$ มีการส่งอัตโนมัติ $u_1$ ถึง $u_2$ และ $v_1$ ถึง $v_2$. โปรดทราบว่าสิ่งนี้แข็งแกร่งกว่า edge-transitivity เนื่องจากเราสามารถระบุวิธีที่จุดสิ้นสุดของแผนที่ขอบไปยังจุดสิ้นสุดของอีกขอบหนึ่งได้ (ดังนั้นกราฟดังกล่าวจึงเรียกอีกอย่างว่าarc-transitive )
ตอนนี้Wikipedia ยืนยันว่ามีกราฟที่เป็นจุดยอด - สกรรมกริยาและขอบ - ทรานซิทีฟ แต่ไม่สมมาตร กราฟดังกล่าวไม่สามารถมีคุณสมบัติการสลับขอบได้มิฉะนั้นเราสามารถส่งจุดยอดที่อยู่ติดกันคู่ใดคู่หนึ่งไปยังอีกคู่ของจุดยอดที่อยู่ติดกันได้โดยใช้การเปลี่ยนขอบจากนั้นจึงสลับขอบหากจำเป็น
เกี่ยวกับการเชื่อมต่อระหว่างจุดยอด - การขนส่ง, การเปลี่ยนขอบและคุณสมบัติการแลกเปลี่ยนขอบ: กราฟปริซึมสามเหลี่ยมมีคุณสมบัติการสลับขอบดังนั้นจึงเป็นจุดยอด - ทรานซิทีฟ แต่ไม่ใช่การเปลี่ยนขอบ ฉันไม่สามารถนึกถึงกราฟที่เป็นจุดยอด - ทรานซิทีฟ แต่ไม่ใช่ edge-transitive และไม่มีคุณสมบัติ edge-swapping ที่ด้านบนของหัวของฉันแม้ว่าฉันจะแปลกใจถ้าไม่มีกราฟดังกล่าว