무어 그래프

수학의 미해결 문제 둘레 5, 차수 57인 무어 그래프는 존재하는가? (더 많은 수학의 미해결 문제 보기)

그래프 이론에서 무어 그래프(Moore graph)는 차수 d , 지름 k이고 꼭짓점 개수가 $1+d\sum _{i=0}^{k-1}(d-1)^{i}$인 정규 그래프이다. 이 개수는 차수와 지름이 주어졌을 때 그래프가 가질 수 있는 정점 개수의 최댓값이다.

무어 그래프의 몇 가지 동등한 정의는 다음과 같다.

• 무어 그래프는 지름이 $k$, 안둘레가 $2k+1$인 그래프이다.
• 꼭지점 $n$개, 변 $m$개를 갖는 무어 그래프는 안둘레가 $g=2k+1$이고 $g$-순환을 ${\frac {n}{g}}(m-n+1)$개 갖는 그래프이다. 이러한 순환의 개수는 그래프의 안둘레 길이에 대해 극단인 경우이다.

무어 그래프라는 이름은 앨런 호프만과 로버트 싱글턴에 의해, 이러한 그래프를 설명하고 분류하는 문제를 제기한 Edward F. Moore의 이름을 따서 명명되었다. (Hoffman & Singleton (1960))

무어 그래프는 차수와 지름이 주어졌을 때 가능한 최대 정점 수를 가질 뿐 아니라, 차수와 둘레가 주어졌을 때 가능한 최소 정점 수를 갖는다. 즉, 모든 무어 그래프는 케이지이다. 무어 그래프의 꼭짓점 수에 대한 공식은 짝수 둘레를 가진 무어 그래프를 허용하도록 일반화될 수 있고, 이러한 그래프 역시 케이지이다.

차수 및 지름에 따른 꼭지점 개수의 상한

페테르센 그래프를 무어 그래프로 나타낸 그림. 모든 너비 우선 탐색 트리의 깊이 i에 d(d − 1)ⁱ 개의 꼭짓점이 있다.

G를 최대 차수 d 와 지름 k를 갖는 임의의 그래프라고 하고, 임의의 꼭지점 v에서 시작하는 너비 우선 탐색에 의해 형성된 나무를 생각하자. 이 나무는 깊이 0(v 자체)에서 1개의 정점을 갖고, 깊이 1(v의 이웃)에서 최대 d개의 정점을 갖는다. 다음 깊이에는 많아야 d (d − 1) 개의 꼭짓점이 있는데, 깊이 1 꼭짓점인 v의 각 이웃은 v에 이미 연결되어 있으므로 깊이 2에서 최대 d − 1개의 이웃을 가질 수 있기 때문이다. 일반적으로, 모든 레벨 1 ≤ i ≤ k에서 많아야 d(d − 1)ⁱ⁻¹개의 정점이 있다. 따라서 정점 개수의 상한은 $1+d\sum _{i=0}^{k-1}(d-1)^{i}$이다.

호프만과 싱글턴은 무어 그래프를 꼭짓점 개수가 이 상한과 일치하는 그래프로 정의하였다. (Hoffman & Singleton (1960)) 따라서, 임의의 무어 그래프는 최대 차수가 d, 직경이 k인 모든 그래프 중에서 가장 많은 꼭짓점을 갖는다.

이후 싱글턴은 무어 그래프를 직경 k, 둘레 2k+1인 그래프로 정의하는 것이 원래 정의와 동등함을 보였다. (Singleton (1968)) 이 두 가지 조건을 동시에 만족하는 그래프는 어떤 d에 대해 d-정규 그래프가 되고, 꼭짓점 계산 공식을 만족한다.

케이지로서의 무어 그래프

그래프의 최대 차수와 지름을 사용하여 꼭짓점 개수에 대한 상한을 만드는 대신, 유사한 방법을 통해 최소 차수와 안둘레를 사용하여 꼭짓점 개수에 대한 하한을 만들 수 있다. 그래프 G의 최소 차수가 d이고 둘레가 2k +1이라고 가정하자. 임의로 시작 정점 v를 선택하고, 이전과 같이 v를 뿌리로 하는 너비 우선 탐색 나무를 만든다. 이 트리는 깊이 0(v 자체)에 하나의 정점이 있고, 깊이 1에서 최소한 d개의 정점이 있다. k > 1의 경우, 깊이 2에 포함된 꼭짓점은 깊이 1 이하의 꼭짓점 두 개 이상과 인접하지 않음을 관찰하자. 그렇지 않다면 가정한 안둘레 2k+1보다 작은 길이의 순환이 형성된다. 따라서 이 경우에는 깊이 2에 적어도 d(d − 1)개의 꼭짓점이 있는데, 깊이 1의 각 꼭짓점에는 깊이 2에서 채워야 할 이웃이 최소한 d − 1개 있고 깊이 1인 서로 다른 꼭짓점은 하나의 레벨 2 꼭짓점과 동시에 이웃하지 않기 때문이다. 일반적으로, 모든 깊이 1 ≤ i ≤ k에서 적어도 d(d − 1)ⁱ 개의 꼭짓점이 있어야 하고, 꼭짓점 개수의 하한은 $1+d\sum _{i=1}^{k-1}(d-1)^{i}$이다.

무어 그래프는 꼭짓점 개수에 대한 하한을 정확히 만족한다. 지름이 k인 각 무어 그래프의 안둘레는 정확히 2k +1이다. 더 긴 안둘레를 가질 만큼 정점이 충분하지 않고, 2k +1보다 더 짧은 주기가 존재하면 너비 우선 탐색 나무의 처음 k 개의 깊이 중 일부에서 정점이 부족하게 된다. 따라서 모든 무어 그래프는, 최소 차수가 d 이고 둘레가 2k +1인 모든 그래프 중에서 꼭짓점이 가장 적다. 따라서 무어 그래프는 케이지이다.

짝수 안둘레 2k에 대해서는 한 변의 중간점에서 시작하는 너비 우선 탐색 나무를 유사하게 구성할 수 있다. 최소 차수가 d 인 이 안둘레의 그래프에서 꼭짓점 개수의 하한에 대한 결과는 다음과 같다.

$2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0}^{k-2}(d-1)^{i}.$

공식의 우변은 앞에서 설명한 방법 대신 단일 정점에서 시작하는 너비 우선 탐색 나무의 꼭짓점 수를 계산한 것으로, 나무의 마지막 레벨에 있는 꼭짓점이 이전 레벨에 있는 꼭짓점 d 개에 인접할 수 있는 가능성을 고려하여 만든 것이다. 무어 그래프는 때때로 이 짝수 안둘레의 경우에서 하한을 정확히 충족하는 그래프를 포함하도록 정의된다. 이러한 경우에도 그래프는 케이지이다.

예시

호프만-싱글턴 정리에 따르면, 둘레가 5인 무어 그래프는 차수가 2, 3, 7 또는 57이다. 무어 그래프는 다음과 같다.

• n > 2에 대해, n개의 꼭지점 위의 완전 그래프 $K_{n}$ (지름 1, 둘레 3, 차수 n − 1, 꼭짓점 n)
• 홀수 차수 순환 그래프 $C_{2n+1}$ (지름 n, 둘레 2 n + 1, 차수 2, 꼭짓점 2 n + 1)
• 페테르센 그래프 (지름 2, 둘레 5, 차수 3, 꼭짓점 10)
• 호프만-싱글턴 그래프 (직경 2, 둘레 5, 차수 7, 꼭짓점 50)
• 존재 여부가 알려지지 않은 가상의 그래프 (직경 2, 둘레 5, 차수 57, 꼭짓점 3250)

알려진 모든 무어 그래프는 꼭짓점 전이 그래프이지만, 알려지지 않은 그래프는 (만약 존재한다면) 꼭짓점 전이 그래프가 될 수 없는데, 자기동형군의 위수가 최대 375이고 이는 꼭짓점 개수보다 작기 때문이다.

짝수 안둘레를 허용하는 무어 그래프의 일반화된 정의를 사용하면 짝수 안둘레 무어 그래프는 (퇴화 가능성이 있는) 일반화 다각형의 인접 그래프에 해당한다. 몇 가지 예로는 다음이 있다.

• 짝수 차수 순환 그래프 $C_{2n}$
• 완전 이분 그래프 $K_{n,n}$ (안둘레 4)
• Heawood 그래프 (차수 3, 안둘레 6)
• Tutte-Coxeter 그래프 (차수 3, 안둘레 8)

더욱 일반적으로, 위에 나열되지 않은 모든 무어 그래프는 안둘레가 5, 6, 8 또는 12여야 하는 것으로 알려져 있다. 짝수 둘레의 경우에는 일반화된 n각형에 대해 n의 가능한 값에 대한 Feit-Higman 정리도 따라야 한다.

같이 보기

• 차수 직경 문제
• 주어진 직경과 최대 차수의 알려진 가장 큰 그래프의 표

참고 문헌

• Azarija, Jernej; Klavžar, Sandi (2015), “Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles”, 《Journal of Graph Theory》 80: 34–42, arXiv:1210.6342, doi:10.1002/jgt.21837, S2CID 333785 
• Bannai, E.; Ito, T. (1973), “On finite Moore graphs”, 《Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics》 20: 191–208, MR 0323615, 2012년 4월 24일에 원본 문서에서 보존된 문서 
• Bollobás, Béla (1998), 《Modern Graph Theory》, Graduate Texts in Mathematics 184, Springer-Verlag 
• Dalfó, C. (2019), “A survey on the missing Moore graph” (PDF), 《Linear Algebra and Its Applications》 569: 1–14, doi:10.1016/j.laa.2018.12.035, hdl:2117/127212, MR 3901732, S2CID 126689579 
• Damerell, R. M. (1973), “On Moore graphs”, 《Mathematical Proceedings of the Cambridge Philosophical Society》 74 (2): 227–236, Bibcode:1973PCPS...74..227D, doi:10.1017/S0305004100048015, MR 0318004 
• Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), “On a problem of graph theory” (PDF), 《Studia Sci. Math. Hungar.》 1: 215–235, 2016년 3월 9일에 원본 문서 (PDF)에서 보존된 문서, 2010년 2월 23일에 확인함 .
• Hoffman, Alan J.; Singleton, Robert R. (1960), “Moore graphs with diameter 2 and 3”, 《IBM Journal of Research and Development》 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437 
• Mačaj, Martin; Širáň, Jozef (2010), “Search for properties of the missing Moore graph”, 《Linear Algebra and Its Applications》 432 (9): 2381–2398, doi:10.1016/j.laa.2009.07.018 
•  Singleton, Robert R. (1968), “There is no irregular Moore graph”, 《American Mathematical Monthly》 75 (1): 42–43, doi:10.2307/2315106, JSTOR 2315106, MR 0225679 

외부 링크

• Brouwer, Haemers: Spectra of graphs
• Weisstein, Eric Wolfgang. Moore Graph (Hoffman-Singleton Theorem). 《Wolfram MathWorld》 (영어). Wolfram Research.