강한 정규 그래프

매개변수 srg(13,6,2,3)를 갖는 강한 정규 그래프인 차수 13의 페일리 그래프 .

그래프 이론에서 강한 정규 그래프는 정규 그래프 중 각 꼭지점 쌍의 공통 이웃의 개수에 대해 추가적인 조건을 가지는 그래프이다. G = (V, E)를 정점 v개를 가지는 k-정규 그래프라고 할 때, 어떤 정수 λ, μ가 존재하여 다음 조건을 만족할 경우 G를 강한 정규 그래프라고 한다.

• 모든 인접한 꼭짓점 쌍은 λ개의 공통 이웃을 갖는다.
• 모든 인접하지 않은 꼭짓점 쌍은 μ개의 공통 이웃을 갖는다.

이 조건을 만족하는 그래프를 srg(v, k, λ, μ)으로 쓰기도 한다. 강한 정규 그래프는 1963년 라지 찬드라 보스에 의해 도입되었다.

일부 저자는 동일한 크기 완전 그래프들의 서로소 합집합 또는 그 여 그래프와 같이 정의를 자명하게 충족시키는 그래프를 제외하기도 한다.

srg(v, k, λ, μ)의 여 그래프는 srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ)으로, 강한 정규 그래프이다.

μ가 0이 아닌 강한 정규 그래프는 직경이 2인 거리 정규 그래프이다. λ = 1인 강한 정규 그래프는 국소적 선형 그래프이다.

성질

매개변수 간의 관계

srg(v, k, λ, μ)의 4개 매개변수는 독립적이지 않고, 다음 관계를 따라야 한다.

$(v-k-1)\mu =k(k-\lambda -1)$

위의 관계는 다음과 같은 조합론적 논증을 통해 도출할 수 있다.

1. 그래프의 꼭짓점이 3개의 깊이에 있다고 상상하자. 깊이 0에 있는 정점 하나를 뿌리로 선택한다. 이 정점의 k개의 이웃은 깊이 1에 있고, 다른 모든 정점은 깊이 2에 있다.
2. 깊이 1인 꼭짓점은 뿌리에 직접 연결되므로 뿌리와 공통되는 다른 이웃 λ개가 있어야 하고, 이러한 공통 이웃은 깊이 1에 있어야 한다. 각 꼭짓점의 차수가 k 이므로 깊이 2 꼭짓점에 연결하기 위한 깊이 1 꼭짓점에 남아 있는 변은 $k-\lambda -1$개이므로, 깊이 1과 깊이 2 사이에는 변 $k(k-\lambda -1)$개가 존재한다.
3. 깊이 2 꼭짓점은 뿌리에 직접 연결되지 않으므로 뿌리와 μ개의 공통 이웃이 있어야 하고, 이러한 공통 이웃은 모두 깊이 1에 있어야 한다. 깊이 2에는 꼭짓점이 $(v-k-1)$개 있고, 각각은 깊이 1 꼭짓점 μ 개와 연결되므로 깊이 1과 깊이 2 사이에는 변 $(v-k-1)\mu$개가 존재한다.
4. 깊이 1과 깊이 2 사이에 있는 변 개수에 대한 두 식을 등호로 연결하여 $(v-k-1)\mu =k(k-\lambda -1)$를 얻는다.

인접행렬

I를 단위행렬, J를 요소가 모두 1인 v × v 행렬이라고 하자. 강한 정규 그래프의 인접행렬 A는 두 방정식을 만족한다.

$AJ=JA=kJ,$

이는 정규 그래프 조건을 간단하게 다시 기술한 것이다. 이것은 k 가 all-one 고유 벡터를 갖는 인접 행렬의 고유값임을 보여준다. 두 번째는 강한 정규성을 나타내는 이차방정식

$A^{2}=kI+\lambda {A}+\mu (J-I-A)$

이다. 좌변의 ij 번째 요소는 i에서 j 까지의 길이 2인 경로의 수이다. 우변의 첫 번째 항은 i에서 자기 자신으로의 경로 수, 즉 자신의 각 이웃에 대해 i에서 이웃으로 갔다가 다시 i로 돌아오는 경로 k개이다. 두 번째 항은 i 와 j 가 직접 연결된 경우 길이 2인 경로의 수를 나타낸다. 세 번째 항은 i 와 j 가 연결되지 않은 경우 길이 2인 경로의 수이다. 세 가지 경우가 상호 배타적이고 집합적으로 완전하므로 위와 같은 등식이 성립한다.

반대로, 인접 행렬이 위의 두 조건을 모두 만족하고 완전 그래프 또는 빈 그래프가 아닌 그래프는 강한 정규 그래프이다.

고윳값

그래프의 인접 행렬에는 정확히 3개의 고윳값이 있다.

• k, 중복도 1
• ${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right],$ 중복도${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
• ${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right],$ 중복도${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$

중복도는 정수여야 하므로 위 표현은 크레인 조건 과 관련된 v, k, μ 및 λ 값에 대한 추가 제약을 준다.

$2k+(v-1)(\lambda -\mu )\neq 0$인 강한 정규 그래프는 중복도가 같지 않은 정수 고유값을 가진다.

$2k+(v-1)(\lambda -\mu )=0$인 강한 정규 그래프는 대칭 회의 행렬과의 연결 때문에 회의 그래프라고 한다. 매개변수는 다음으로 감소한다.

$\operatorname {srg} \left(v,{\frac {1}{2}}(v-1),{\frac {1}{4}}(v-5),{\frac {1}{4}}(v-1)\right).$

반대로, 3개의 고유값만을 가지는 연결된 정규 그래프는 강한 정규 그래프이다.

예

• 길이 5인 순환 그래프는 srg(5, 2, 0, 1)이다.
• 페테르센 그래프는 srg(10, 3, 0, 1)이다.
• Clebsch 그래프는 srg(16, 5, 0, 2)이다.
• Shrikhande 그래프는 거리 전이 그래프가 아닌 srg(16, 6, 2, 2)이다.
• n × n 룩 그래프, 즉 균형 잡힌 완전 이분 그래프 K_{n, n} 의 선 그래프는 srg(n², 2 n - 2, n - 2, 2)이다. n = 4일 때, 매개변수는 Shrikhande 그래프의 매개변수와 같지만 두 그래프는 동형이 아니다.
• 완전 그래프 K_n의 선 그래프는 ${\textstyle \operatorname {srg} \left({\binom {n}{2}},2(n-2),n-2,4\right)}$이다.
• Chang 그래프는 srg(28, 12, 6, 4)로 매개변수가 K₈의 선 그래프와 같지만 이 4개의 그래프는 동형이 아니다.
• 일반화된 사변형 GQ(2, 4)의 선 그래프는 srg(27, 10, 1, 5)이다. 사실 모든 일반화된 차수(s, t)의 사각형은 다음과 같은 방식으로 강한 정규 그래프를 제공한다. 즉, srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1).
• Schläfli 그래프는 srg(27, 16, 10, 8)이다.
• 호프만-싱글턴 그래프는 srg(50, 7, 0, 1)이다.
• Sims-Gewirtz 그래프는 (56, 10, 0, 2)이다.
• M₂₂ 그래프는 srg(77, 16, 0, 4)이다.
• Brouwer-Haemers 그래프는 srg(81, 20, 1, 6)이다.
• 히그먼-심스 그래프는 srg(100, 22, 0, 6)이다.
• 국소 매클로플린 그래프는 srg(162, 56, 10, 24)이다.
• Cameron 그래프는 srg(231, 30, 9, 3)이다.
• Berlekamp-van Lint-Seidel 그래프는 srg(243, 22, 1, 2)이다.
• 매클로플린 그래프는 srg(275, 112, 30, 56)이다.
• 차수 q 의 페일리 그래프는 srg(q, (q - 1)/2, (q - 5)/4, (q - 1)/4)이다. 가장 작은 페일리 그래프(q = 5인 경우)는 5-순환 그래프이다.
• 자기 보완 호 전이 그래프는 강한 정규 그래프이다.

강한 정규 그래프와 그 여 그래프가 모두 연결되어 있는 경우 원시적이라고 한다. 위에서 제시된 모든 그래프는 원시적이다. 원시적이지 않은 강한 정규 그래프는 μ = 0 또는 λ = k 의 매개변수를 가진다.

콘웨이의 99-그래프 문제는 srg(99, 14, 1, 2)의 구성을 묻는 문제이다. 이러한 매개변수가 있는 그래프가 존재하는지 여부는 알려져 있지 않으며 존 호턴 콘웨이는 이 문제에 대한 해결책으로 1000달러의 상금을 제안하였다.

같이 보기

• 부분 기하학
• 자이델 인접 행렬
• 2 그래프

참고 문헌

• AE Brouwer, AM Cohen 및 A. Neumaier(1989), Distance Regular Graphs. 베를린, 뉴욕: Springer-Verlag.ISBN 3-540-50619-5ISBN 3-540-50619-5 ,ISBN 0-387-50619-5
• Chris Godsil 및 Gordon Royle(2004), Algebraic Graph Theory. 뉴욕: Springer-Verlag.ISBN 0-387-95241-1ISBN 0-387-95241-1

외부 링크

• Eric W. Weisstein, Mathworld 기사, 다양한 예.
• Gordon Royle, 더 큰 그래프족 목록.
• Andries E. Brouwer, 강한 정규 그래프의 매개변수.
• Brendan McKay, 일부 그래프 모음.
• Ted Spence, 최대 64개의 정점에 대한 강한 정규 그래프.