거리 정규 그래프

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

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

교차 배열

직경 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle d } 의 그래프 $G$에 대해, 정수 배열 $\{b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d}\}$이 존재하여 모든 $1\leq j\leq d$과 거리가 $j$인 $G$의 꼭짓점 쌍 $u$, $v$에 대해 $v$와의 거리가 $j+1$인 $u$의 이웃이 $b_{j}$개이고 $v$와의 거리가 $j-1$인 $u$의 이웃이 $c_{j}$개인 경우, $G$는 거리 정규 그래프이다. 거리 정규 그래프를 특징짓는 이 정수 배열을 교차 배열(intersection array)이라고 한다.

공스펙트럼 거리 정규 그래프

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

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

성질

$G$를 차수 $k$이고 교차 배열 $\{b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d}\}$을 갖는 연결 거리 정규 그래프라고 하자. 모든 $0\leq j\leq d$에 대해 $G_{j}$를 $G$에서 거리가 $j$인 꼭짓점 쌍을 연결하여 얻은 $k_{j}$-정규 그래프라고 하고, 그 인접 행렬을 $A_{j}$이라고 하자. 거리 $j$인 꼭짓점 쌍 $u$, $v$에 대해, $v$와의 거리가 $j$인 $u$의 이웃의 개수를 $a_{j}$라고 하자.

그래프 이론적 성질

• 모든 $0\leq j<d$에 대해 ${\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}$이다.
• $b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0$이고, $1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}$이다.

스펙트럼 성질

• $G$가 완전 다분 그래프(complete multipartite graph)가 아닌 한, $G$의 모든 고유값 중복도 $m>1$에 대해 $k\leq {\frac {1}{2}}(m-1)(m+2)$이다.
• $G$가 완전 다분 그래프가 아닌 한, $G$의 모든 고유값 중복도 $m>1$에 대해 $d\leq 3m-4$이다.
• $\lambda$가 $G$의 단순 고유값인 경우 $\lambda \in \{\pm k\}$이다.
• $G$는 $d+1$개의 서로 다른 고윳값을 갖는다.

만약에 $G$가 강한 정규 그래프인 경우 $n\leq 4m-1$이고 $k\leq 2m-1$이다.

예

종수 3의 유향 표면에 포함된 7차 클라인 그래프 및 관련 지도. 이 그래프는 교차 배열 {7,4,1;1,2,7} 및 자기동형군 PGL(2,7)을 갖는 거리 정규 그래프이다.

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

• 완전 그래프
• 순환 그래프
• 홀 그래프
• 무어 그래프
• 웰스 그래프와 실베스터 그래프
• 직경 2의 강한 정규 그래프

거리-정규 그래프의 분류

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

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

3차 거리 정규 그래프

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

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

추가 자료

• Godsil, C. D. (1993). 《Algebraic combinatorics》. Chapman and Hall Mathematics Series. New York: Chapman and Hall. xvi+362쪽. ISBN 978-0-412-04131-0. MR 1220704.