대칭 그래프

어떤 그래프 $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 그래프와 같은 의미이다.