범순환 그래프

Pancyclic graph
8면체 그래프에서 가능한 모든 길이의 사이클로, 범순환형임을 나타냅니다.

그래프 이론의 수학적 연구에서, 범순환 그래프는 그래프에서 [1]3개에서 꼭지점 수까지 가능한 모든 길이의 주기를 포함하는 유향 그래프 또는 무향 그래프입니다.범순환 그래프는 가능한 최대 길이의 주기를 갖는 해밀턴 그래프의 일반화이다.

정의들

해당 범위에 드는 모든 k{k\displaystyle}에게, 3≤ k, G{\displaystyle 3\leq k\leq n\, ,G}길이의 순환이 포함되어 있≤ k{k\displaystyle}.[1]그것은 또는vertex-pancyclic 만약, 모든 꼭지점 v와 같은 범주 안의 모든 k의 길이 k의 포함하는 멀티 사이클이 포함되어 있node-pancyclic v.[2] n-vertex 그래프 Gpancyclic 있다.Simil같은 범위의 모든 가장자리 e와 모든 k에 대해 [2]e를 포함하는 길이 k의 사이클을 포함하는 경우 엣지 범순환이다.

초당 그래프는 홀수 길이의 사이클을 포함하지 않기 때문에 범순환형일 수 없지만, 4에서 [3]n까지의 모든 짝수 길이의 사이클을 포함하는 경우에는 이환형이라고 합니다.

평면 그래프

최대 외측평면 그래프는 평면 내의 단순한 폴리곤이 내측을 삼각측량하여 형성된 그래프이다.모든 최대 외평면 그래프는 유도에서 알 수 있듯이 범순환형이다.그래프의 바깥쪽 면은 n-vertex 사이클이며, 그래프의 나머지 부분에 연결된 삼각형을 하나만 제거하면(삼각형의 이중 그래프를 구성하는 나무의 잎) 하나의 더 적은 정점에 최대 외평면 그래프를 형성하며, 유도에 의해 나머지 길이의 주기가 모두 생긴다.제거할 삼각형을 선택할 때 같은 인수가 모든 최대 외부 평면 그래프가 노드 [4]범순환형임을 더 강하게 보여줍니다.예를 들어 휠 그래프와 같이 최대 외부 평면 스패닝 하위 그래프가 있는 그래프도 마찬가지입니다.

최대 평면 그래프는 모든 면, 심지어 외부 면까지 삼각형인 평면 그래프입니다.최대 평면 그래프는 해밀턴 [5]사이클이 있는 경우에만 노드 범순환형이다. 해밀턴 사이클이 아닌 경우 범순환형이 아니며, 해밀턴 사이클의 내부는 동일한 노드에서 최대 외측 평면 그래프에 대한 이전 인수를 [6]적용할 수 있다.예를 들어, 이 그림은 6개의 정점이 있는 해밀턴식 최대 평면 그래프인 8면체 그래프의 범순환성을 보여준다.더 강하게, 같은 인수에 의해, 최대 평면 그래프가 길이 k의 주기를 갖는다면, 그것은 모두 더 작은 [7]길이의 주기를 가진다.

길이 8을 제외한 모든 길이의 사이클이 최대 n인 거의 범순환형 할린 그래프

할린 그래프는 나무의 모든 잎을 연결하는 도면에 사이클을 추가하여 도수가 2개인 평면의 도면에서 형성되는 평면 그래프입니다.할린 그래프는 반드시 범순환형일 필요는 없지만, 최소한 하나의 누락된 사이클 길이가 있다는 점에서 거의 범순환형이다.누락된 주기의 길이는 반드시 짝수입니다.할린 그래프의 내부 꼭지점 중 3도가 없는 경우 반드시 [8]범순환형이어야 합니다.

Bondy(1971)는 해밀턴 사이클의 존재에 대한 많은 고전적 조건도 그래프가 범순환적이기에 충분한 조건이라고 관찰했으며, 이를 바탕으로 모든 4연결 평면 그래프가 범순환적이라고 추측했다.하지만, Malkevitch(1971)는 반례의 일족을 발견했다.

토너먼트

토너먼트는 각 정점 쌍 사이에 하나의 방향 가장자리가 있는 방향 그래프입니다.직관적으로 토너먼트를 사용하여 라운드 로빈 스포츠 경기를 모델링할 수 있으며, 각 경기의 승자와 패자의 우위를 점할 수 있습니다.토너먼트는 패자와 승자의 L과 W가 아닌 두 개의 서브셋으로 분할할 수 없는 경우에만 강하게 연결되거나 강하게 연결된다. W의 모든 선수가 L의 [9]모든 경쟁자를 이길 수 있다. 모든 강력한 토너먼트는 범순환적이고[10] 노드 [11]범순환적이다.정규 토너먼트가 있는 경우(각 선수의 승패 수가 서로 동일함), 에지 판사이클링(edge-pancyclic)[12]이지만, 4개의 정점이 있는 강한 토너먼트는 에지 판사이클링(edge-pancyclic)이 될 수 없다.

모서리가 많은 그래프

Mantel의 정리는 최소 n2/4개의 모서리를 가지며 다중 모서리나 자기 루프가 없는 모든 n-vertex 무방향 그래프는 삼각형을 포함하거나 완전한 초당n/2,n/2 그래프 K라고 말한다.이 정리는 강화될 수 있다: 최소 n2/4개의 모서리를 가진 무방향 해밀턴 그래프는 범순환형 또는n/2,n/2 [1]K이다.

n(n + 1)/2 - 3 에지를 가진 n-vertex Hamiltonian 방향 그래프는 범순환이 아니지만, 적어도 n(n + 1)/2 - 1 에지를 가진 모든 해밀턴 방향 그래프는 범순환이다.또한 각 정점이 적어도 n도(착신 및 발신 에지를 함께 카운트)를 갖는 n-vertex 강접속 방향 그래프는 범순환형 또는 완전한 초당 방향 [13]그래프이다.

그래프 파워

그래프 G에서 k번째 거듭제곱k G는 G에서 거리가 최대 k인 두 꼭지점 사이에 모서리가 있는 동일한 꼭지점 집합의 그래프로 정의됩니다.만약 G가 2-vertex 연결된다면, Fleischner의 정리에 의해 그것의2 제곱 G는 해밀턴이다; 이것은 그것이 꼭 꼭지점-범환이라는 [14]것을 보여주기 위해 강화될 수 있다.더 강하게, G가 해밀턴일 때2, 그것은 또한 범순환이다.[15]

계산의 복잡성

3연결 입방체 그래프의 특수한 경우에도 그래프가 범순환인지 여부를 테스트하는 것은 NP-완전이며, 다면체 그래프의 [16]특수한 경우에도 그래프가 노드-범순환인지를 테스트하는 것도 NP-완전이다.그래프의 제곱이 해밀턴인지, 따라서 [17]범순환인지 여부를 검사하는 것도 NP-완전입니다.

역사

범순환성은 하라리와 모저(1966년), 문(1966년), 알스파흐(1967년)에 의해 토너먼트의 맥락에서 처음 조사되었다.범순환성의 개념은 Bondy(1971년)에 의해 명명되고 무방향 그래프로 확장되었다.

메모들

  1. ^ a b c 본디(1971년).
  2. ^ a b 랜더라스 외 (2002).
  3. ^ Schmeichel & Mitchem (1982)
  4. ^ Li, Corneil & Mendelson(2000), 제안 2.5.
  5. ^ Helden (2007), Collollary 3.78.
  6. ^ Bernhart & Kainen(1979년).
  7. ^ 하키미&슈메이첼(1979년).
  8. ^ 스코우로스카(1985년).
  9. ^ Harary & Moser(1966), Corollary 5b.
  10. ^ Harary & Moser(1966), 정리 7.
  11. ^ 문(1966), 정리 1.
  12. ^ Alspach(1967).
  13. ^ Hégkvist & Thomassen(1976년).
  14. ^ 홉스(1976년).
  15. ^ 플라이슈네르(1976년).
  16. ^ Li, Corneil & Mendelson(2000),이론 2.3 및 2.4
  17. ^ 지하(1978년).

레퍼런스

  • 를 클릭합니다Alspach, Brian (1967), "Cycles of each length in regular tournaments", Canadian Mathematical Bulletin, 10 (2): 283–286, doi:10.4153/cmb-1967-028-6.
  • 를 클릭합니다Bernhart, Frank; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2.
  • 를 클릭합니다Bondy, J. A. (1971), "Pancyclic graphs I", Journal of Combinatorial Theory, Series B, 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5.
  • 를 클릭합니다Fleischner, H. (1976), "In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts", Monatshefte für Mathematik, 82 (2): 125–149, doi:10.1007/BF01305995, MR 0427135.
  • 를 클릭합니다Häggkvist, Roland; Thomassen, Carsten (1976), "On pancyclic digraphs", Journal of Combinatorial Theory, Series B, 20 (1): 20–40, doi:10.1016/0095-8956(76)90063-0.
  • 를 클릭합니다Hakimi, S. L.; Schmeichel, E. F. (1979), "On the number of cycles of length k in a maximal planar graph", Journal of Graph Theory, 3: 69–86, doi:10.1002/jgt.3190030108.
  • 를 클릭합니다Harary, Frank; Moser, Leo (1966), "The theory of round robin tournaments", American Mathematical Monthly, 73 (3): 231–246, doi:10.2307/2315334.
  • 를 클릭합니다Helden, Guido (2007), Hamiltonicity of maximal planar graphs and planar triangulations (PDF), Dissertation, Rheinisch-Westfälischen Technischen Hochschule Aachen, archived from the original (PDF) on 2011-07-18.
  • 를 클릭합니다Hobbs, Arthur M. (1976), "The square of a block is vertex pancyclic", Journal of Combinatorial Theory, Series B, 20 (1): 1–4, doi:10.1016/0095-8956(76)90061-7, MR 0416980.
  • 를 클릭합니다Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics, 98 (3): 219–225, doi:10.1016/S0166-218X(99)00163-8.
  • 를 클릭합니다Malkevitch, Joseph (1971), "On the lengths of cycles in planar graphs", Recent Trends in Graph Theory, Lecture Notes in Mathematics, vol. 186, Springer-Verlag, pp. 191–195, doi:10.1007/BFb0059437.
  • 를 클릭합니다Moon, J. W. (1966), "On subtournaments of a tournament", Canadian Mathematical Bulletin, 9 (3): 297–301, doi:10.4153/CMB-1966-038-7.
  • 를 클릭합니다Randerath, Bert; Schiermeyer, Ingo; Tewes, Meike; Volkmann, Lutz (2002), "Vertex pancyclic graphs", Discrete Applied Mathematics, 120 (1–3): 219–237, doi:10.1016/S0166-218X(01)00292-X.
  • 를 클릭합니다Schmeichel, Edward; Mitchem, John (1982), "Bipartite graphs with cycles of all even lengths", Journal of Graph Theory, 6 (4): 429–439, doi:10.1002/jgt.3190060407.
  • 를 클릭합니다Skowrońska, Mirosława (1985), "The pancyclicity of Halin graphs and their exterior contractions", in Alspach, Brian R.; Godsil, Christopher D. (eds.), Cycles in Graphs, Annals of Discrete Mathematics, vol. 27, Elsevier Science Publishers B.V., pp. 179–194.
  • 를 클릭합니다Underground, Polly (1978), "On graphs with Hamiltonian squares", Discrete Mathematics, 21 (3): 323, doi:10.1016/0012-365X(78)90164-4, MR 0522906.

외부 링크