무어 그래프

수학에서 해결되지 않은 문제:

둘레가 5, 정도가 57인 무어 그래프가 존재합니까?

그래프 이론에서 무어 그래프(Moore graph)는 지름(가장 긴 두 꼭짓점 사이의 거리)의 두 배 이상인 정규 그래프입니다.이러한 그래프의 정도가 $d$ 이고 지름이 $k$ 인 경우, 그래프의 둘레는 $2k$ + $1$ 이어야 합니다.이것은 d $및$ 지름 $k$ 의 그래프의 경우 정점의 수가 동일한 경우에만 성립합니다.

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

이 정도와 지름을 가진 그래프에서 가능한 한 가장 큰 정점의 상한입니다.따라서 이러한 그래프는 모수에 대한 차수 지름 문제를 해결합니다.

무어 그래프 $G$ 의 또 다른 동등한 정의는 g의 $girth$ g = $2k$ + $1$ 과 정확하게 $n / g$ $(m$ – $n$ + $1)$ 사이클을 갖는다는 것입니다. 여기서 $n$ 과 $m$ 은 각각 $G$ 의 꼭짓점과 모서리의 개수입니다.이들은 실제로 그래프의 둘레를 길이로 하는 사이클 수에 대해 극단적입니다.^[1]

무어 그래프는 Hoffman & Singleton(1960)이 에드워드 F의 이름을 따서 명명했습니다. 이 그래프들을 설명하고 분류하는 문제를 제기한 무어.

무어 그래프는 주어진 차수와 지름의 조합에서 가능한 최대 정점 수를 가질 뿐만 아니라, 주어진 차수와 둘레를 갖는 정규 그래프에서 가능한 최소 정점 수를 갖습니다.즉, 무어 그래프는 모두 케이지(cage)입니다.^[2]무어 그래프의 정점 수에 대한 공식은 홀수 둘레뿐만 아니라 짝수 둘레를 갖는 무어 그래프를 정의할 수 있도록 일반화될 수 있으며, 이 그래프들은 다시 케이지(cages)입니다.

차수 및 직경별 정점 경계 설정

피터슨 그래프는 무어 그래프입니다.너비 첫 번째 검색 트리에는 i번째 수준에 $d (d$ - $1) i$ 개의 정점이 있습니다.

$G$ 를 최대 d, $직경$ $k$ 의 그래프라고 하고, 임의의 정점 $v$ 에서 시작하는 너비 첫 번째 검색으로 형성된 트리를 생각해보십시오.이 트리는 레벨 0( $v$ 자체)에 1개의 정점이 있고 레벨 1( $v$ 의 이웃)에 최대 $d개$ 의 정점이 있습니다.다음 수준에서는 최대 $d (d$ - $1)$ 개의 정점이 있습니다. $v$ 의 각 이웃은 인접 관계 중 하나를 사용하여 $v$ 에 연결하므로 수준 2에서 $최대$ d - $1개$ 의 이웃을 가질 수 있습니다.일반적으로 유사한 인수는 수준 1≤ $i$ ≤ $k$ 에서 최대 $d (d$ - $1) i -1$ 개의 정점이 있을 수 있음을 보여줍니다.따라서 최대 정점의 총 개수는 다음과 같을 수 있습니다.

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

Hoffman & Singleton(1960)은 원래 무어 그래프를 정점 수에 대한 이러한 경계가 정확히 충족되는 그래프로 정의했습니다.따라서 모든 무어 그래프는 최대 도수 $d$ 와 $직경$ k를 갖는 모든 그래프 중에서 가능한 최대 정점 수를 가집니다.

나중에 싱글턴(1968)은 무어 그래프가 직경 $k$ 와 둘레 $2k$ + $1$ 을 갖는 것으로 동등하게 정의될 수 있음을 보여주었습니다. 이 두 가지 요구 사항은 그래프를 어떤 $d$ 에 대해 d-규칙적이 되도록 하고 정점 계산 공식을 만족시키기 위해 결합됩니다.

무어는 우리와 같은 그래프를 그립니다.

그래프의 최대 정도와 지름으로 정점의 수를 상한으로 하는 대신, 우리는 유사한 방법을 통해 최소 정도와 둘레로 정점의 수에 대한 하한을 계산할 수 있습니다.^[2] $G$ 의 최소 차수 $d$ 와 둘레 $2k$ + $1$ 을 갖는다고 가정하자. 시작 정점 $v$ 를 임의로 선택하고, 이전과 같이 $v$ 에 근을 둔 너비 우선 검색 트리를 생각하자.이 트리는 레벨 0( $v$ 자체)에 하나의 정점을 가지고, 레벨 1에 $적어도$ d개의 정점을 가지고 있어야 합니다.레벨 2에서( $k$ > $1$ 인 경우), $최소$ d $(d$ - $1)$ 개의 정점이 있어야 합니다. 레벨 1의 각 정점에는 채워야 할 $적어도$ d - $1개$ 의 나머지 인접이 있고, 레벨 1의 두 정점은 서로 인접하거나 레벨 2의 공유 정점에 인접할 수 없으므로 가정된 둘레보다 짧은 사이클이 생성됩니다.일반적으로 유사한 인수를 사용하면 $수준 1$ ≤ i ≤ $k$ 에서 최소한 $d (d$ - $1) i$ 개의 정점이 있어야 합니다.따라서 정점의 총 개수는 적어도 다음과 같아야 합니다.

1+d\sum _{i=1}^{k-1}(d-1)^{i}

무어 그래프에서 정점 수에 대한 이 경계는 정확히 충족됩니다.각 무어 그래프의 둘레는 정확히 $2k$ + $1$ 입니다. 더 높은 둘레를 가질 만큼 충분한 정점을 가지고 있지 않으며, 더 짧은 주기는 너비의 첫 번째 검색 트리의 첫 $k$ 수준에 정점이 너무 적을 것입니다.따라서, 모든 무어 그래프는 최소 $차수$ d와 둘레 $2k$ + $1$ 을 갖는 모든 그래프 중에서 가능한 최소 정점 수를 갖는데, 이는 케이지(cage)입니다.

짝수 둘레 $2k$ 의 경우에도 마찬가지로 너비 우선 검색 트리를 단일 에지의 중간 지점에서 시작할 수 있습니다.최소 차수 $d$ 를 갖는 이 둘레 그래프의 최소 정점 개수에 대한 결과 경계는

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

(공식의 오른쪽은 대신 하나의 정점에서 시작하는 너비 첫 번째 검색 트리의 정점 수를 세고, 트리의 마지막 수준에 있는 정점이 이전 수준의 $d개$ 정점에 인접할 가능성을 설명합니다.)따라서 무어 그래프는 때때로 이 경계를 정확히 충족하는 그래프를 포함하는 것으로 정의됩니다.다시 말하지만, 이러한 그래프는 케이지(cage)여야 합니다.

예

호프만-싱글턴 정리에 따르면 둘레가 5인 무어 그래프는 2, 3, 7, 또는 57도를 가져야 합니다.무어 그래프는 다음과 같습니다.^[3]

완전 그래프 $Kn n$ > $2개$ 의 노드 (직경 1, 둘레 3, 차수 $n$ - $1$ , 차수 $n$ )
홀수 사이클 $C 2 n +1$ ( $직경$ , 둘레 $2n$ + $1$ , 도 2, $순서$ 2n + $1$ )
페테르센 그래프(직경 2, 둘레 5, 도 3, 순서 10)
호프만-싱글턴 그래프(직경 2, 둘레 5, 도 7, 순서 50)
존재를 알^[4] 수 없는 지름 2, 둘레 5, 도 57 및 차수 3250의 가상 그래프

알려진 무어 그래프는 모두 정점 전이 그래프이지만, 알려지지 않은 그래프(존재하는 경우)는 정점 수보다 적은 375개의 순서를 가질 수 있기 때문에 정점 전이 그래프가 될 수 없습니다.^[5]

짝수 둘레 그래프를 허용하는 무어 그래프의 일반화된 정의를 사용하는 경우 짝수 둘레 무어 그래프는 (퇴행 가능성이 있는) 일반화된 다각형의 입사 그래프에 해당합니다.몇 가지 예로는 짝수 사이클 $C 2 n$ , 둘레가 4인 완전한 이분 그래프 $K n, n$ , 각도가 3이고 둘레가 6인 Heawood 그래프, 각도가 3이고 둘레가 8인 Tutte-Coxeter 그래프가 있습니다.일반적으로 위에 나열된 그래프를 제외한 모든 무어 그래프의 둘레는 5, 6, 8 또는 12가 되어야 하는 것으로 알려져 있습니다.^[6]짝수 둘레의 경우도 일반화된 n-곤에 대한 $n$ 의 가능한 값에 대한 Feit-Higman 정리를 따릅니다.

참고 항목

주어진 직경과 최대 정도에 대해 알려진 가장 큰 그래프의 표

메모들

^ 아자리야 & 클라브 ž르 (2015).
^ ^a ^b 에르드 ő스, 레니와 소스 (1966).
^ Bolobás (1998), 정리 19, p. 276.
^ Dalfo (2019)
^ 마카즈 & 시라 ň (2010).
^ 반나이 & 이토 (1973); 데임렐 (1973)

참고문헌

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, archived from the original on 2012-04-24
Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 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, archived from the original (PDF) on 2016-03-09, retrieved 2010-02-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

외부 링크

브라우어와 헤머: 그래프의 스펙트럼
Eric W. Weisstein, Moore Graph (Hoffman-Singleton Theorem) at MathWorld.

[FOOTNOTEAzarijaKlavžar2015-1] 아자리야 & 클라브 ž르 (2015).

[FOOTNOTEErdősRényiSós1966-2] 에르드 ő스, 레니와 소스 (1966).

[FOOTNOTEBollobás1998Theorem_19,_p._276-3] Bolobás (1998), 정리 19, p. 276.

[FOOTNOTEDalfó2019-4] Dalfo (2019)

[FOOTNOTEMačajŠiráň2010-5] 마카즈 & 시라 ň (2010).

[6] 반나이 & 이토 (1973); 데임렐 (1973)

[1]

[2]

[3]

[4]

[5]

[6]

Search