거리 정규 그래프

틀:위키데이터 속성 추적 수학에서 거리 정규 그래프(틀:Llang)는 임의의 두 꼭짓점 v, w 에 대해 v와의 거리가 j이고 w와의 거리가 k인 꼭짓점 수가 j, k 및 v와 w 사이의 거리에만 의존하는 정규 그래프이다.

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

교차 배열

직경 $d$ 의 그래프 $G$ 에 대해, 정수 배열 ${b_{0}, b_{1}, \dots, b_{d - 1}; c_{1}, \dots, 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}, \dots, b_{d - 1}; c_{1}, \dots, 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 \dots \geq b_{d - 1} > 0$ 이고, $1 = c_{1} \leq \dots \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 3 m - 4$ 이다.
$λ$ 가 $G$ 의 단순 고유값인 경우 $λ \in {\pm k}$ 이다.
$G$ 는 $d + 1$ 개의 서로 다른 고윳값을 갖는다.

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

예

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

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