대칭 그래프

어떤 그래프 $G$에 대해, 변의 연결 상태를 보존하는 자기동형사상 $f$가 존재할 경우, 그 사상을 그래프의 대칭성이라고 정의한다. 여기에서 연결 상태를 보존한다는 의미는, 그래프 $G$에 속하는 변 $(u,v)$, $(u',v')$에 대해, $f(u)=u',f(v)=v'$가 성립한다는 의미이다. 대칭성이 존재하는 그래프를 대칭 그래프(symmetric graph)라고 부른다.

페테르센 그래프는 대칭 그래프의 하나이다.

정의를 확장해서, 어떤 그래프에 대해서 길이가 $k$인 호(arc)를 보존하지만 길이가 $k+1$인 호를 보존하지는 않는 자기동형사상이 있을 경우, 그 그래프는 $k$-arc-transitive라고 부른다. 변은 길이가 1인 호이므로, 대칭 그래프는 1-arc-transitive 그래프와 같은 의미이다.