둘레(그래프 이론)

Girth (graph theory)

그래프 이론에서, 비방향 그래프의 둘레는 그래프에 포함된 최단 주기의 길이다.[1]그래프에 사이클이 없는 경우(즉, 숲) 그 둘레는 무한대로 정의된다.[2]예를 들어, 4주기(제곱)의 둘레는 4이다.격자에는 둘레가 4이고, 삼각망에는 둘레가 3이다.둘레가 4 이상인 그래프는 삼각형이 없다.

케이지

가능한 한 작은 둘레 g의 입방 그래프(모든 꼭지점은 3도)는 g-cage(또는 (3,g)-cage)로 알려져 있다.피터슨 그래프는 독특한 5-케이지(둘째 5의 가장 작은 입방 그래프), 헤이우드 그래프는 독특한 6-케이지, 맥기 그래프는 독특한 7-케이지, 투트 8 케이지가 독특한 8-케이지다.[3]주어진 둘레에 대해 여러 개의 케이지가 존재할 수 있다.예를 들어, 세 개의 비이등형 10-cage가 있으며 각각 70개의 정점을 가지고 있다: 발라반 10-cage, 해리스 그래프, 해리스-웡 그래프.

둘레 및 그래프 컬러링

모든 양의 정수 g와 χ에 대해 둘레 최소 g와 색수를 가진 그래프가 존재한다. 예를 들어, 그뢰츠슈 그래프는 삼각형이 없고 색수 4를 가지고 있으며, 그뢰츠슈 그래프를 형성하는 데 사용되는 미켈스키안 구조를 반복하면 임의로 큰 색수의 삼각형이 없는 그래프가 생성된다.Paul Erdős는 확률론적 방법을 사용하여 일반적인 결과를 처음으로 증명했다.[4]보다 정확하게, 그는 확률 n을(1 − g)/g 가진 각 가장자리를 포함시킬지 여부를 독립적으로 선택함으로써 형성된 n 정점에 대한 무작위 그래프는, n이 무한대로 가는 확률로, 길이 g 또는 그 이하의 최대 n/2 사이클에서, n/2k 크기의 독립된 집합은 가지고 있지 않음을 보여주었다.따라서 각 짧은 주기로부터 하나의 꼭지점을 제거하면 g보다 큰 둘레가 있는 작은 그래프가 남는데, 이 그래프는 색상의 각 색 등급이 작아야 하므로 모든 색상에서 적어도 k가지 색상이 필요하다.

크긴 하지만 명시적으로 둘레와 색수가 높은 그래프는 유한한 필드 위에 있는 선형 그룹의 특정 Cayley 그래프로 구성할 수 있다.[5]이 주목할 만한 라마누잔 그래프들은 또한 큰 확장 계수를 가지고 있다.

관련개념

그래프의 홀수 둘레와 짝수 둘레는 각각 최단 홀수 사이클과 최단 짝수 사이클의 길이다.

그래프의 원주는 가장 짧은 주기가 아니라 가장 긴(단순) 주기의 길이다.

비삼각주기의 최소 길이로 생각되는 둘레는 수축기하 기하학에서 1-시스트롤 이상의 시스톨로 자연 일반화를 인정한다.

Girth는 평면 그래프의 Girth가 그것의 듀얼 그래프의 가장자리 연결이라는 점에서 가장자리 연결에 대한 이중 개념이다.이러한 개념은 매트로이드에 설정된 가장 작은 종속성의 크기인 매트로이드의 둘레에 의해 매트로이드 이론으로 통일된다.그래픽 매트로이드의 경우 매트로이드 둘레는 기본 그래프의 둘레와 같고, 동그래픽 매트로이드의 경우 에지 연결과 같다.[6]

참조

  1. ^ R. Diestel, 그래프 이론, 페이지 8. 제3판, Springer-Verlag, 2005.
  2. ^ Weisstein, Eric W., "Girth", MathWorld
  3. ^ Brouwer, Andries E., Cages. Distance-Regular Graphs (Brower, Cohen and Neumaer 1989, Springer-Verlag)의 전자 부록.
  4. ^ Erdős, Paul (1959), "Graph theory and probability", Canadian Journal of Mathematics, 11: 34–38, doi:10.4153/CJM-1959-003-9.
  5. ^ Davidoff, Giuliana; Sarnak, Peter; Valette, Alain (2003), Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge, doi:10.1017/CBO9780511615825, ISBN 0-521-82426-5, MR 1989434
  6. ^ Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi:10.1016/j.dam.2007.06.015, MR 2365057.