거리 정규 그래프

1. 개요

거리 정규 그래프는 그래프 이론에서 사용되는 그래프의 한 종류이다. 그래프의 지름 d에 대해, 모든 거리 j (1 ≤ j ≤ d)에 있는 두 정점 u, v에 대해, v와의 거리가 j+1인 u의 이웃이 b_j개이고, v와의 거리가 j-1인 u의 이웃이 c_j개인 정수 배열 {b_0, b_1, ..., b_{d-1}; c_1, ..., c_d}가 존재하면, 해당 그래프는 거리 정규 그래프이다. 이 정수 배열을 교차 배열이라고 하며, 그래프의 교차수 a_j, b_j, c_j는 a_j + b_j + c_j = k를 만족한다. 거리 정규 그래프는 교차 배열을 가질 필요충분조건을 가지며, 완전 그래프, 순환 그래프, 홀 그래프 등이 예시로 존재한다. 3차 거리 정규 그래프는 완전히 분류되어 있으며, 13개의 고유한 그래프가 존재한다.

2. 교차 배열

거리 정규 그래프는 교차 배열이라는 정수 배열로 특징지어진다. 동일한 교차 배열을 갖는 두 연결 거리 정규 그래프는 코스펙트럴이다. 이는 두 그래프의 인접 행렬이 동일한 스펙트럼을 가질 때 성립한다.

거리 정규 그래프가 단절 그래프일 필요충분 조건은 코스펙트럴 거리 정규 그래프의 분리 합집합인 경우이다.

2.1. 정의

직경 $d$인 그래프 $G$에 대해, 정수 배열 $\backslash \{\; b\_0,\; b\_1,\; \backslash ldots,\; b\_\{d-1\};\; c\_1,\; \backslash ldots,\; c\_d\; \backslash \}$이 존재하고, 모든 $1\; \backslash leq\; j\; \backslash leq\; d$와 거리가 $j$인 $G$의 꼭짓점 쌍 $u$, $v$에 대해 $v$와의 거리가 $j+1$인 $u$의 이웃이 $b\_j$개이고 $v$와의 거리가 $j\; -\; 1$인 $u$의 이웃이 $c\_j$개일 때, $G$는 거리 정규 그래프이다. 거리 정규 그래프를 특징짓는 이 정수 배열을 교차 배열(intersection array)이라고 한다.

거리 정규 그래프의 교차 배열은 $(\; b\_0,\; b\_1,\; \backslash ldots,\; b\_\{d-1\};\; c\_1,\; \backslash ldots,\; c\_d\; )$ 형태의 배열이다. 여기서 $d$는 그래프의 지름이며, 각 $1\; \backslash leq\; j\; \backslash leq\; d$에 대해 $b\_j$는 거리 $j+1$에 있는 $v$의 이웃 중에서 $u$의 이웃의 개수를, $c\_j$는 거리 $j\; -\; 1$에 있는 $v$의 이웃 중에서 $u$의 이웃의 개수를 나타낸다. 이는 $u$와 $v$가 거리 $j$에 있는 임의의 두 정점 쌍에 대해 정의된다. 또한 $a\_j$는 $v$로부터 거리 $j$에 있는 $u$의 이웃의 개수를 나타낸다. $a\_j,\; b\_j,\; c\_j$는 그래프의 교차수라고 불린다. 이들은 $a\_j\; +\; b\_j\; +\; c\_j\; =\; k$라는 식을 만족하며, 여기서 $k\; =\; b\_0$는 임의의 정점의 차수, 즉 이웃의 개수이다.

지름이 $d$인 그래프 $G$가 거리 정규 그래프가 되는 필요충분조건은 위에 언급된 교차 배열을 갖는 것이다.

2.2. 교차수

$a\_j,\; b\_j,\; c\_j$는 그래프의 교차수라고 불리며, 이들은 $a\_j\; +\; b\_j\; +\; c\_j\; =\; k$를 만족한다. 여기서 $k\; =\; b\_0$는 정점의 차수이다.

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

동일한 교차 배열을 갖는 두 연결 거리 정규 그래프는 공스펙트럼이다. 거리 정규 그래프의 연결은 공스펙트럼 거리 정규 그래프들의 서로소 합집합인 경우에만 끊어진다.

3. 성질

만약 $G$가 교차 배열 $(\; b\_0,\; b\_1,\; \backslash ldots,\; b\_\{d-1\};\; c\_1,\; \backslash ldots,\; c\_d\; )$를 갖는 차수 $k$의 연결된 거리 정규 그래프라고 가정하자. 각 $0\; \backslash leq\; j\; \backslash leq\; d$에 대해, $k\_j$를 주어진 정점으로부터 거리가 $k$인 정점의 개수로 하고, $G\_\{j\}$를 $G$에서 거리가 $j$인 정점 쌍을 연결하여 형성된 인접 행렬 $A\_j$를 갖는 $k\_\{j\}$-정규 그래프로 나타낸다.

3.1. 그래프 이론적 성질

모든 에 대해 $\backslash frac\{k\_\{j+1\}\}\{k\_\{j\}\}\; =\; \backslash frac\{b\_\{j\}\}\{c\_\{j+1\}\}$이다. 여기서 $k\_j$는 주어진 정점으로부터 거리가 $j$인 정점의 개수이다.

또한, $b\_0\; >\; b\_1\; \backslash geq\; \backslash cdots\; \backslash geq\; b\_\{d-1\}\; >\; 0$이고, $1\; =\; c\_1\; \backslash leq\; \backslash cdots\; \backslash leq\; c\_d\; \backslash leq\; b\_0$이다.

3.2. 스펙트럼 성질

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

4. 예

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

5. 거리-정규 그래프의 분류

주어진 차수 k > 2에 대해, 서로 다른 연결된 거리 정규 그래프는 유한 개만 존재한다.

마찬가지로, 완전 다분 그래프를 제외하면 주어진 고유값 중복도 m > 2에 대해, 서로 다른 연결된 거리 정규 그래프는 유한 개만 존재한다.

5.1. 3차 거리 정규 그래프

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

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