사이클 더블 커버

Cycle double cover
수학의 미해결 문제:

모든 브리지가 없는 그래프에는 모든 에지를 정확하게 두 번 덮는 여러 사이클이 있는가?

(수학에서 더 풀리지 않은 문제)
투영 평면에 헤미도면체로서 포함시키는 것에 해당하는 피터슨 그래프의 주기적 이중 커버.

그래프-이론 수학에서 사이클 이중 커버는 그래프의 각 가장자리를 정확히 두 번 포함하는 비방향 그래프의 사이클 모음입니다.예를 들어, 모든 다면 그래프의 경우 그래프를 나타내는 볼록 다면체의 면은 그래프의 이중 커버를 제공한다. 각 가장자리는 정확히 두 면에 속한다.

그것은 조지 세케레스와[1] 폴 시모어가[2] 제기한 미해결 문제로서, 모든 브릿지 없는 그래프에 사이클 이중 커버가 있는지 여부를 사이클 이중 커버 추측으로 알려져 있다.이러한 추측은 그래프 내장형 측면에서 동등하게 공식화될 수 있으며, 그러한 맥락에서 순환 내장형 추측이라고도 한다.

공식화

통상적으로 사이클 이중 커버 추측의 공식화는 모든 브리지리스 비방향 그래프에 사이클의 컬렉션이 있는지 여부를 질문하여 그래프의 각 가장자리가 사이클의 정확히 두 개에 포함되도록 한다.그래프가 브리지가 없다는 요건은 브리지가 어떤 사이클에도 속할 수 없기 때문에 그러한 사이클 집합이 존재하기 위해 분명히 필요한 조건이다.사이클 이중 커버 추측 조건을 만족하는 사이클의 컬렉션을 사이클 이중 커버라고 한다.사이클 그래프와 브리지리스 선인장 그래프와 같은 일부 그래프는 동일한 사이클을 두 번 이상 사용해야만 커버할 수 있으므로, 이러한 종류의 복제는 사이클 이중 커버에서 허용된다.

스나크로 감소

참고 항목: 스나크(그래프 이론)

스나크는 브리지가 없는 그래프의 특별한 경우로서, 모든 꼭지점에 정확히 세 개의 입사 엣지(그래프는 세제곱)가 있고, 그래프의 가장자리를 세 개의 완벽한 일치(그래프는 3-엣지 색상이 없으며, 바이징의 정리에는 색도 지수 4가 있음)로 분할할 수 없는 추가적인 특성이 있다.스나크는 사이클 이중 커버 추측의 유일한 어려운 경우를 형성하고 있는 것으로 밝혀졌다: 스나크의 추측이 사실이라면, 그것은 어떤 그래프에서도 사실이다.[3]

Jaeger(1985)는 사이클 이중 커버 추측에 대한 잠재적 최소 누적 표본에서 모든 정점에는 3개 이상의 입사 에지가 있어야 한다고 본다.단 하나의 가장자리 인시던트가 브리지(bridge)를 형성하는 반면, 두 가장자리가 꼭지점에서 인시던트(incident)인 경우, 작은 그래프의 이중 커버가 원래 그래프 중 하나로 확장되도록 작은 그래프를 형성하도록 수축할 수 있다.반면, 정점 v에 4개 이상의 입사 모서리가 있는 경우, 두 개의 가장자리를 그래프에서 제거하고 다른 두 끝점을 연결하는 단일 가장자리로 교체하여 결과 그래프의 브리지리스도를 보존함으로써 두 개의 가장자리를 "분할" 수 있다.다시, 결과 그래프의 이중 커버는 원래 그래프의 이중 커버로 직접 확장될 수 있다. 분할된 그래프의 모든 사이클은 원래 그래프의 사이클에 해당하거나 v에서 만나는 사이클 쌍에 해당된다.따라서, 모든 최소 단위 표본은 입방체여야 한다.그러나 입방형 그래프가 가장자리를 3색(빨간색, 파란색, 녹색으로 표현)으로 할 수 있다면, 빨간색과 파란색 가장자리의 하위 그래프, 파란색과 녹색 가장자리의 하위 그래프, 빨간색과 녹색 가장자리의 하위 그래프는 각각 그래프의 모든 가장자리를 두 번 덮는 분리 주기 모음을 형성한다.따라서 최소의 모든 counterexample은 3-edge-colorable bridge-less 입방 그래프, 즉 snark가 되어야 한다.[3]

축소 가능한 구성

사이클 이중 커버 문제에 대한 한 가지 가능한 공격은 어떤 그래프가 축소 가능한 구성, 즉 사이클 이중 커버의 존재 또는 비존재성을 보존하는 방식으로 소형 서브그래프로 대체될 수 있는 하위 그래프를 포함한다는 것을 증명함으로써 최소 counterrexample이 존재할 수 없음을 보여주는 것이다.예를 들어, 입방형 그래프가 삼각형을 포함하는 경우, Δ-Y 변환은 삼각형을 하나의 꼭지점으로 대체한다; 작은 그래프의 사이클 더블 커버는 원래 입방형 그래프의 사이클 더블 커버로 다시 확장될 수 있다.따라서 사이클 이중 커버 추측에 대한 최소의 counterexample은 삼각형이 들어 있는 티에체 그래프와 같은 일부 스낵을 배제한 삼각형이 없는 그래프여야 한다.컴퓨터 검색을 통해 큐빅 그래프에서 길이 11 이하의 모든 사이클이 축소 가능한 구성을 형성하므로 사이클 이중 커버 추정에 대한 최소 카운트렉스 샘플은 둘레가 12개 이상이어야 한다고 알려져 있다.[4]

유감스럽게도, 유한 집합의 환원 가능한 구성을 사용하여 사이클 이중 커버 추측을 증명할 수 없다.모든 환원 가능한 구성은 주기를 포함하므로, 환원 가능한 구성의 모든 유한 집합 S에 대해 집합의 모든 구성이 최대 γ 길이의 주기를 포함하도록 숫자 γ이 있다.그러나 임의적으로 둘레가 높은 스나크, 즉 최단 주기의 길이에 임의적으로 높은 한계가 있는 스나크가 존재한다.[5]둘레가 γ보다 큰 스나크 G는 세트 S의 어떤 구성도 포함할 수 없으므로, S의 감소는 G가 최소 counterexample일 가능성을 배제하기에 충분히 강하지 않다.

원형내장 추측

그래프에 사이클 더블커버가 있으면 커버의 사이클을 이용해 2차원 셀 콤플렉스에 내장된 그래프의 2셀을 형성할 수 있다.입방 그래프의 경우, 이 콤플렉스는 항상 다지관을 형성한다.내장의 모든 면이 그래프에서 단순한 사이클이라는 점에서 그래프는 다지관에 원형적으로 내장되어 있다고 한다.그러나 3도 이상의 그래프의 주기 이중 커버는 다지관에 내장되어 있지 않을 수 있다. 커버의 사이클에 의해 형성된 셀 복합체는 정점에 비매니폴드 위상이 있을 수 있다.원형 내장 추측 또는 강한 내장 추측에[3] 따르면 모든 바이콘 연결 그래프는 다지관에 원형 내장되어 있다.만일 그렇다면, 그래프에는 내장 면에 의해 형성된 사이클 이중 커버도 있다.

입방형 그래프의 경우, 쌍방향성 및 무교량성이 동등하다.따라서, 원형 내장 추측은 적어도 사이클 이중 커버 추측만큼 강력하다.하지만, 그것은 더 강하지 않은 것으로 밝혀졌다.그래프 G의 정점을 확대하여 세제곱 그래프를 형성하고, 그 다음 원형 내장하고, 추가된 가장자리를 수축시켜 팽창이 풀리면, 그 결과는 G 자체가 원형 내장되는 것이 된다.따라서 만약 사이클 이중 커버 추측이 사실이라면, 모든 바이콘넥트 그래프는 원형 임베딩이 된다.즉, 사이클 더블 커버와 원형 임베딩이 항상 같은 것은 아니지만 사이클 더블 커버 추측은 원형 임베딩 추측과 동일하다.[3]

원형 임베딩이 존재하는 경우, 최소 속 표면에는 다음과 같은 속성이 없을 수 있다.Nguyen Huy Shuong은 원형 임베딩이 토러스 위에 놓여 있지 않은 바이코넥티드 토로이드 그래프를 묘사했다.[3]

더 강력한 추측 및 관련 문제

또한 고려된 원형 내장 추측의 더 강력한 버전은 모든 바이콘 연결 그래프가 방향성 다지관에 원형 내장되어 있다는 추측이다.사이클 이중 커버 추정에 있어 이는 사이클 이중 커버가 존재한다는 추측과 동일하며, e를 커버하는 두 사이클이 e를 통해 반대 방향으로 향하도록 커버의 각 사이클에 대한 방향이다.[3]

또는 커버의 사이클 색상을 포함하는 추측의 강화도 고려되었다.이 중 가장 강한 것은 모든 무교량 그래프에는 얼굴이 5색일 수 있는 방향성 다지관에 원형 내장되어 있다는 추측이다.만약 사실이라면, 이것은 모든 브리지가 없는 그래프에 0이 없는 5-흐름이 있다는 W. T. Tutte의 추측을 의미할 것이다.[3]

원형 임베딩보다 더 강한 유형의 임베딩은 다면 임베딩으로, 모든 면이 단순한 사이클이고 교차하는 두 면마다 하나의 꼭지점 또는 단일 가장자리에서 그렇게 하도록 표면에 그래프를 임베딩한다.(입방 그래프의 경우 교차하는 두 면마다 하나의 가장자리에서 그렇게 하도록 요구 사항으로 단순화할 수 있다.)따라서 주기의 이중 커버 추측이 스나크로 감소한다는 관점에서, 스나크의 다면 임베딩에 대해 조사하는 것이 관심이다.그런 임베딩을 찾을 수 없었던 브란코 그룬바움은 존재하지 않는다고 추측했지만, 코철(2009a, 2009b)은 다면 임베딩이 있는 스네이크를 발견함으로써 그룬바움의 억측을 반증했다.

피터슨 컬러링 추측도 참조하십시오.

메모들

  1. ^ 세케레스(1973년).
  2. ^ 시모어(1980).
  3. ^ a b c d e f g 재거(1985년).
  4. ^ 허크(2000).
  5. ^ 코철(1996년).

참조

  • Fleischner, Herbert (1976), "Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen", Monatshefte für Mathematik, 81 (4): 267–278, doi:10.1007/BF01387754.
  • Huck, A. (2000), "Reducible configurations for the cycle double cover conjecture", Discrete Applied Mathematics, 99 (1–3): 71–90, doi:10.1016/S0166-218X(99)00126-2.
  • Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1.
  • Kochol, Martin (1996), "Snarks without small cycles", Journal of Combinatorial Theory, Series B (1 ed.), 67 (1): 34–47, doi:10.1006/jctb.1996.0032.
  • Kochol, Martin (2009a), "3-Regular non 3-edge-colorable graphs with polyhedral embeddings in orientable surfaces", Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani, Lecture Notes in Computer Science, vol. 5417, pp. 319–323.
  • Kochol, Martin (2009b), "Polyhedral embeddings of snarks in orientable surfaces", Proceedings of the American Mathematical Society (5 ed.), 137 (05): 1613–1619, doi:10.1090/S0002-9939-08-09698-6.
  • Seymour, P. D. (1980), "Disjoint paths in graphs", Discrete Mathematics, 29 (3): 293–309, doi:10.1016/0012-365X(80)90158-2.
  • Szekeres, G. (1973), "Polyhedral decomposition of cubic graphs", Bulletin of the Australian Mathematical Society, 8 (03): 367–387, doi:10.1017/S0004972700042660.
  • Zhang, Cun-Quan (1997), Integer Flows and Cycle Covers of Graphs, CRC Press, ISBN 978-0-8247-9790-4.
  • Zhang, Cun-Quan (2012), Circuit Double Cover of Graphs, Cambridge University Press, ISBN 978-0-5212-8235-2.

외부 링크