토로이드 그래프

Toroidal graph
14개의 정점이 토러스 위에 포함된 입방형 그래프
히우드 그래프와 관련 지도가 토러스 안에 포함되어 있다.

수학에서 toroidal graph는 torus에 삽입될 수 있는 그래프를 말한다.즉, 그래프의 정점을 가장자리가 교차하지 않도록 토러스 위에 배치할 수 있다.

예

평면에 삽입할 수 있는 모든 그래프는 토러스에도 삽입될 수 있다.속 1의 토로이드 그래프는 토러스에는 포함될 수 있지만 평면에는 포함될 수 없다.히우드 그래프, 전체 그래프 K7(따라서 K와5 K6), 피터슨 그래프(따라서 피터슨 그래프에 하위분할이 포함되어 있기 때문에 완전한 양분 그래프3,3 K), 블라누샤 스나크 중 하나,[1] 그리고 모든 뫼비우스 사다리들은 환상형이다.보다 일반적으로 교차 번호가 1인 그래프는 모두 환상적이다.교차 번호가 더 큰 일부 그래프도 toroidal이다. 예를 들어, Möbius-Kantor 그래프는 교차 번호 4를 가지고 있고 toroidal이다.[2]

특성.

어떤 토로이드 그래프라도 색수는 최대 7이다.[3]전체 그래프 K는7 색도 번호 7의 토로이드 그래프의 예를 제공한다.[4]

삼각형이 없는 모든 토로이드 그래프는 최대 4의 색수를 가진다.[5]

파리의 정리와 유사한 결과에 의해, 어떤 토로이드 그래프는 주기적인 경계 조건이 있는 직사각형의 직선 가장자리로 그려질 수 있다.[6]나아가 투테의 봄 정리의 아날로그가 이 경우에 적용된다.[7]Toroidal 그래프에는 또한 최대 7페이지의 책이 내장되어 있다.[8]

장애물

By the Robertson-세이모어 정리, 최소 비토로이드 그래프의 유한 집합 H가 존재하며, H에 그래프 부전위가 없는 경우에만 그래프가 토로이드인 것이다.즉, H는 토로이드 그래프에 대해 금지된 미성년자 집합을 형성한다.전체 집합 H는 알 수 없지만 최소 17,523개의 그래프를 가지고 있다.또는 위상학적 부차 순서에서 최소인 최소 250,815개의 비좌상 그래프가 있다.위상학적 부차로서 이러한 그래프가 없는 경우에만 그래프가 환상적이다.[9]

갤러리

참고 항목

메모들

  1. ^ 오르바니치 외 (2004).
  2. ^ 마루시치 & 피산스키(2000년).
  3. ^ 희우드(1890).
  4. ^ 샤르트랑과 장(2008).
  5. ^ 크롱크&화이트(1972년).
  6. ^ 코케이, 닐슨 & 시지파우스키(2001).
  7. ^ Gortler, Gotsman & Thurston(2006).
  8. ^ 엔도(1997년).
  9. ^ 미럴드 & 우드콕(2018).

참조

  • Chartrand, Gary; Zhang, Ping (2008), Chromatic graph theory, CRC Press, ISBN 978-1-58488-800-0.
  • Endo, Toshiki (1997), "The pagenumber of toroidal graphs is at most seven", Discrete Mathematics, 175 (1–3): 87–96, doi:10.1016/S0012-365X(96)00144-6, MR 1475841.
  • Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), "Discrete one-forms on meshes and applications to 3D mesh parameterization" (PDF), Computer Aided Geometric Design, 23 (2): 83–112, doi:10.1016/j.cagd.2005.05.002, MR 2189438.
  • Heawood, P. J. (1890), "Map colouring theorems", Quarterly Journal of Mathematics, First Series, 24: 322–339.
  • Kocay, W.; Neilson, D.; Szypowski, R. (2001), "Drawing graphs on the torus" (PDF), Ars Combinatoria, 59: 259–277, MR 1832459, archived from the original (PDF) on 2004-12-24, retrieved 2018-09-06.
  • Kronk, Hudson V.; White, Arthur T. (1972), "A 4-color theorem for toroidal graphs", Proceedings of the American Mathematical Society, American Mathematical Society, 34 (1): 83–86, doi:10.2307/2037902, JSTOR 2037902, MR 0291019.
  • Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Math. Slovaca, 50: 117–121[permanent dead link].
  • Myrvold, Wendy; Woodcock, Jennifer (2018), "A large set of torus obstructions and how they were discovered", Electronic Journal of Combinatorics, 25 (1): P1.16, doi:10.37236/3797
  • Neufeld, Eugene; Myrvold, Wendy (1997), "Practical toroidality testing", Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 574–580.
  • Orbanić, Alen; Pisanski, Tomaž; Randić, Milan; Servatius, Brigitte (2004), "Blanuša double", Math. Commun., 9 (1): 91–103.