거리 정규 그래프

수학에서 거리 정규 그래프()는 임의의 두 꼭짓점 v, w 에 대해 v와의 거리가 j이고 w와의 거리가 k인 꼭짓점 수가 j, k 및 v와 w 사이의 거리에만 의존하는 정규 그래프이다.

모든 거리 전이 그래프는 거리 정규 그래프이다. 실제로, 거리 정규 그래프는 거리 전이 그래프의 일반화로서 도입되었고, 반드시 큰 자기동형군을 갖지 않고도 거리 전이 그래프의 수치적인 규칙성을 갖는다.

교차 배열 
직경 의 그래프 에 대해, 정수 배열 이 존재하여 모든 과 거리가 인 의 꼭짓점 쌍 , 에 대해 와의 거리가 인 의 이웃이 개이고 와의 거리가 인 의 이웃이 개인 경우, 는 거리 정규 그래프이다. 거리 정규 그래프를 특징짓는 이 정수 배열을 교차 배열(intersection array)이라고 한다.

공스펙트럼 거리 정규 그래프 
한 쌍의 연결 거리 정규 그래프는 동일한 교차 배열이 있는 경우에만 공스펙트럼이다.

거리 정규 그래프의 연결은 공스펙트럼 거리 정규 그래프들의 서로소 합집합인 경우에만 끊어진다.

성질 
를 차수 이고 교차 배열 을 갖는 연결 거리 정규 그래프라고 하자. 모든 에 대해 를 에서 거리가 인 꼭짓점 쌍을 연결하여 얻은 -정규 그래프라고 하고, 그 인접 행렬을 이라고 하자. 거리 인 꼭짓점 쌍 , 에 대해, 와의 거리가 인 의 이웃의 개수를 라고 하자.

그래프 이론적 성질 

 모든 에 대해 이다.
 이고, 이다.

스펙트럼 성질 

 가 완전 다분 그래프(complete multipartite graph)가 아닌 한, 의 모든 고유값 중복도 에 대해  이다.
 가 완전 다분 그래프가 아닌 한, 의 모든 고유값 중복도 에 대해 이다.
  가 의 단순 고유값인 경우 이다.
 는 개의 서로 다른 고윳값을 갖는다.

만약에 가 강한 정규 그래프인 경우 이고 이다.

예 

거리 정규 그래프의 예는 다음과 같다.

 완전 그래프
 순환 그래프
 홀 그래프
 무어 그래프
 웰스 그래프와 실베스터 그래프

 직경 2의 강한 정규 그래프

거리-정규 그래프의 분류 
주어진 차수 를 갖는 서로 다른 연결된 거리 정규 그래프의 개수는 유한하다.

유사하게, 완전 다분 그래프를 제외하면 주어진 고유값 중복도 를 갖는 서로 다른 연결된 거리 정규 그래프의 개수는 유한하다.

3차 거리 정규 그래프 
3차 거리 정규 그래프는 완전히 분류되었다.

13개의 고유한 3차 거리 정규 그래프는 K4 (또는 사면체 그래프), K3,3, 페테르센 그래프, 정육면체 그래프, 헤우드 그래프, 파푸스 그래프, 콕서터 그래프, 텃-콕서터 그래프, 정십이면체 그래프, 데자르그 그래프, 텃 12-케이지, 빅스–스미스 그래프 및 포스터 그래프이다.

참고 문헌

추가 자료 

 
정규 그래프
그래프족
대수적 그래프 이론