Вершинная транзитивность и свойство перестановки ребер

Question

Простой неориентированный граф $G=(V,E)$называется вершинно-транзитивным, если для любого$a,b\in V$ есть изоморфизм графов $\varphi:V\to V$ такой, что $\varphi(a) = b$.

Мы говорим, что граф $G=(V,E)$имеет свойство смены краев, если для любого края$e = \{x,y\} \in E$ есть изоморфизм графов $\varphi:V\to V$ такой, что $\varphi(x) = y$ и $\varphi(y) = x$.

Подразумевает ли одно из этих свойств другое для связных графов?

Answer 1

Как говорит Экин в комментариях, для связных графов свойство смены ребер подразумевает транзитивность вершин посредством компоновки смены ребер вдоль пути.

Другой вывод неверен. Граф является симметричным, если для любой пары смежных вершин$(u_1,v_1)$ и $(u_2,v_2)$ есть отправка автоморфизма $u_1$ к $u_2$ и $v_1$ к $v_2$. Обратите внимание, что это сильнее, чем транзитивность ребра, потому что мы можем указать способ отображения концевых точек ребра в конечные точки другого ребра (следовательно, такой граф также называется дуго-транзитивным ).

Теперь Википедия утверждает, что существуют графы, транзитивные по вершинам и ребрам, но не симметричные. Такой граф не может обладать свойством смены ребер, иначе мы могли бы отправить любую пару соседних вершин другой паре соседних вершин, используя транзитивность ребер, а затем, при необходимости, поменять ребро местами.

Что касается связи между транзитивностью вершин, транзитивностью ребер и свойством смены ребер: треугольный призматический граф имеет свойство смены ребер и, следовательно, он транзитивен по вершинам, но не является транзитивным по ребрам. Я не могу придумать граф, который является вершинно-транзитивным, но не реберно-транзитивным, и у меня в голове не возникает свойства смены ребер, хотя я был бы удивлен, если бы таких графов не было.