정점 이동 및 가장자리 스와핑 속성
단순한 무 방향 그래프 $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$.
이러한 속성 중 하나가 연결된 그래프에 대해 다른 속성을 의미합니까?
답변
Ekin이 주석에서 말했듯이 연결된 그래프의 경우 edge-swapping 속성은 경로를 따라 edge swap을 구성함으로써 vertex-transitivity를 의미합니다.
다른 의미는 사실이 아닙니다. 인접한 정점 쌍에 대한 그래프는 대칭 입니다.$(u_1,v_1)$ 과 $(u_2,v_2)$ automorphism 전송이 있습니다 $u_1$ ...에 $u_2$ 과 $v_1$ ...에 $v_2$. 에지의 끝 점이 다른 에지의 끝점에 매핑되는 방식을 지정할 수 있기 때문에 (따라서 이러한 그래프를 arc-transitive 라고도 합니다 ) 이는 에지 이동보다 더 강력 합니다.
이제 Wikipedia는 정점 전이 및 가장자리 전이이지만 대칭이 아닌 그래프가 있다고 주장 합니다. 그러한 그래프는 edge-swapping 속성을 가질 수 없습니다. 그렇지 않으면 edge-transitivity를 사용하여 인접 정점 쌍을 다른 쌍의 인접 정점으로 보내고 필요한 경우 edge를 교환 할 수 있기 때문입니다.
정점-전이, 가장자리-전이 및 가장자리-스와핑 속성 간의 연결과 관련하여 삼각 프리즘 그래프 에는 가장자리-스와핑 속성이 있으므로 정점-전이이지만 가장자리-전이는 아닙니다. 나는 정점 전이이지만 가장자리 전이가 아닌 그래프를 생각할 수 없으며 그러한 그래프가 없다면 놀랄 것입니다.