케이지(그래프 이론)

그래프 이론의 수학적 영역에서 케이지(cage)는 둘레에 대해 가능한 한 정점이 적은 정규 그래프다.

형식적으로 (r,g)-그래프는 각 정점에 정확히 r 이웃이 있고, 최단 주기의 길이가 정확히 g인 그래프로 정의된다. 안(r,g)-케이지(cage)는 모든 (r,g)-그래프 중에서 정점 수가 가장 적은 (r,g)-그래프다.a(3,g)-cage는 흔히 g-cage라고 불린다.

r ≥ 2와 g ≥ 3의 어떤 조합에도 (r,g)-그래프가 존재한다고 알려져 있다.그것은 모든 (r,g)-cage가 존재한다는 것을 따른다.

무어 그래프가 도 r과 둘레 g와 함께 존재한다면 그것은 케이지임에 틀림없다.게다가, 무어 그래프의 크기에 대한 한계는 우리에 일반화된다: 홀수 둘레 g를 가진 모든 케이지에는 최소한 그 이상이 있어야 한다.

${\displaystyle 1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}}}}$

정점, 그리고 짝수 g를 가진 모든 케이지에는 적어도 하나가 있어야 한다.

${\displaystyle 2\sum _{i=0}^{(g-2)/2}(r-1)^{i}}}}$

정점정확히 이렇게 많은 정점을 가진 모든 (r,g)-그래프는 정의상 무어 그래프여서 자동으로 케이지가 된다.

r과 g의 특정 조합에 대해 여러 개의 케이지가 존재할 수 있다.예를 들어, 세 개의 비이등형(3,10)-케이지가 있으며 각각 70개의 정점을 가지고 있다: 발라반 10-케이지, 해리 그래프, 해리-웡 그래프.그러나 발라반 11-케이지(112 꼭지점)는 하나뿐이다.

알려진 우리

1-정규 그래프는 주기가 없고, 연결된 2-정규 그래프는 둘레가 정점 수와 같기 때문에, 우리들은 r 3 3에만 관심이 있다.(r,3)-케이지는 r+1 정점에 대한 완전한 그래프_r+1 K이고, (r,4)-케이지는 2r 정점에 대한 완전한 초당적 그래프 K이다_r,r.

주목할 만한 우리에는 다음이 포함된다.

• (3,5)-케이지: Petersen 그래프, 10정점
• (3,6)-케이지: 히우드 그래프, 14정점
• (3,8)-카이지: Tutte-Coxeter 그래프, 30 꼭지점
• (3,10)-케이지: 발라반 10-케이지, 70 꼭지점
• (3,11)-케이지: 발라반 11-케이지, 112 정점
• (4,5)-카이지: 로버슨 그래프, 19개의 꼭지점
• (7,5)-기호:호프만-싱글턴 그래프, 50정점.
• r - 1이 주 전력일 때 (r,6) 케이지는 투영 평면의 발생 그래프다.
• r - 1이 주력이면 (r,8) 및 (r,12) 케이지가 일반화된 폴리곤이 된다.

돌출면과 일반화된 다각형을 제외한 r > 2와 g > 2의 값에 대해 알려진 (r,g) 우리에 있는 정점의 수는 다음과 같다.

g r	3	4	5	6	7	8	9	10	11	12
3	4	6	10	14	24	30	58	70	112	126
4	5	8	19	26	67	80				728
5	6	10	30	42		170				2730
6	7	12	40	62		312				7812
7	8	14	50	90

점증약학

g의 큰 값의 경우, 무어 바운드는 정점 수 n이 g의 함수로서 적어도 하나의 기하급수적으로 증가해야 함을 의미한다. 동등하게, g는 n의 로그에 최대 비례할 수 있다.더 정확하게

${\displaystyle g\leq 2\log _{r-1}n+O(1)}$

이 바운드는 단단하거나 단단하다고 여겨진다(Bollobas & Szemerédi 2002).g에 대해 가장 잘 알려진 하한선도 로그이지만 상수인자가 더 작다(n이 단일 지수적으로 증가하지만 무어 바운드보다 더 높은 비율로 성장한다).구체적으로, 루보츠키, 필립스 & 사르나크(1988)가 정의한 라마누잔 그래프의 구성은 바운드를 만족시킨다.

${\displaystyle g\geq {\frac {4}{3}\log _{r-1}n+O(1)}$

이 바운드는 라제브니크, 우스티멘코 & 볼다르(1995)에 의해 약간 개선되었다.

이 그래프들 자체가 우리일 가능성은 낮지만, 그 존재는 우리에 필요한 정점의 수에 상한선을 둔다.

참조

• Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge Mathematical Library, pp. 180–190, ISBN 0-521-45897-8.
• Bollobás, Béla; Szemerédi, Endre (2002), "Girth of sparse graphs", Journal of Graph Theory, 39 (3): 194–200, doi:10.1002/jgt.10023, MR 1883596.
• Exoo, G; Jajcay, R (2008), "Dynamic Cage Survey", Dynamic Surveys, Electronic Journal of Combinatorics, DS16, archived from the original on 2015-01-01, retrieved 2012-03-25.
• 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.
• Hartsfield, Nora; Ringel, Gerhard (1990), Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, pp. 77–81, ISBN 0-12-328552-6.
• Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, pp. 183–213, ISBN 0-521-43594-3.
• Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J. (1995), "A new series of dense graphs of high girth", Bulletin of the American Mathematical Society, New Series, 32 (1): 73–79, arXiv:math/9501231, doi:10.1090/S0273-0979-1995-00569-0, MR 1284775.
• Lubotzky, A.; Phillips, R.; Sarnak, P. (1988), "Ramanujan graphs", Combinatorica, 8 (3): 261–277, doi:10.1007/BF02126799, MR 0963118.
• Tutte, W. T. (1947), "A family of cubical graphs", Proc. Cambridge Philos. Soc., 43 (4): 459–474, Bibcode:1947PCPS...43..459T, doi:10.1017/S0305004100023720.

외부 링크

• 브루워, 안드리스 E. 케이지
• 로일, 고든큐빅 케이지 및 고탄도 케이지
• Weisstein, Eric W. "Cage Graph". MathWorld.