トロイダルグラフ

数学のグラフ理論の分野において、トーラスグラフはトーラス上に埋め込むことができるグラフです。言い換えると、グラフの頂点と辺は、両方に属する頂点以外では辺が交差しないようにトーラス上に配置できます。

平面に埋め込むことができるグラフはトーラスにも埋め込むことができるため、すべての平面グラフはトーラスグラフでもあります。平面に埋め込むことができないトーラスグラフは、種数1であると言われています。

ヒーウッドグラフ、完全グラフK ₇ (したがって K ₅と K ₆ )、ピーターセングラフ(したがって完全二部グラフK _3,3。ピーターセングラフにはその細分が含まれるため)、ブラヌーシャスナークの 1 つ、^[1]、およびすべてのメビウスラダーはトーラス状です。より一般的には、交差数が 1 のグラフはすべてトーラス状です。交差数が大きいグラフもトーラス状です。たとえば、メビウス・カンターグラフは交差数が 4 でトーラス状です。^[2]

任意のトーラスグラフの彩色数は最大で7である。 ^[3]完全グラフK7_は彩色数が7であるトーラスグラフの例である。^[4]

三角形のないトロイダルグラフの彩色数は最大4である。^[5]

ファリの定理に類似した結果により、任意のトーラスグラフは、周期境界条件を持つ長方形内に直線の辺で描くことができる。^[6]さらに、この場合、トゥッテのバネ定理 の類似が適用されます。 ^[7] トーラスグラフには、最大7ページの本の埋め込みもあります。 ^[8]

ロバートソン・シーモア定理によれば、極小非トーラスグラフの有限集合Hが存在し、グラフがトーラスであるためにはHにグラフマイナーが存在しない必要がある。つまり、H はトーラスグラフの禁制マイナー集合を形成する。完全な集合Hは不明だが、少なくとも 17,523 個のグラフが存在する。あるいは、位相的マイナー順序において極小となる非トーラスグラフが少なくとも 250,815 個存在する。グラフがトーラスであるためには、これらのグラフが位相的マイナーとして存在しない必要がある。^[9]

• 
  四元数群の2 つの同型ケーリーグラフ。
• 
  トーラスに埋め込まれた四元数群のケーリー グラフ。
• トーラスに埋め込まれた四元数群のケーリーグラフのビデオ。
• 
  トーラスに埋め込まれたパップス グラフと関連マップ。

• 平面グラフ
• 位相グラフ理論
• チャーサール多面体

• チャートランド、ゲイリー、チャン、ピン（2008）、クロマティックグラフ理論、CRCプレス、ISBN 978-1-58488-800-0。
• 遠藤俊樹 (1997)、「トロイダルグラフのページ数は最大7である」、離散数学、175 (1–3): 87–96、doi :10.1016/S0012-365X(96)00144-6、MR  1475841。
• Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006)、「メッシュ上の離散 1 フォームと 3D メッシュ パラメータ化への応用」(PDF)、Computer Aided Geometric Design、23 (2): 83–112、doi :10.1016/j.cagd.2005.05.002、MR  2189438、S2CID  135438。
• Heawood, PJ (1890)、「地図色定理」、純粋および応用数学季刊誌、第 1 シリーズ、24 : 322–339。
• Kocay, W.; Neilson, D.; Szypowski, R. (2001)、「トーラス上のグラフの描画」(PDF)、Ars Combinatoria、59 : 259–277、MR 1832459、2004-12-24に オリジナル(PDF)からアーカイブ、 2018-09-06 に取得。
• Kronk, Hudson V.; White, Arthur T. (1972)、「トロイダルグラフの 4 色定理」、アメリカ数学会紀要、34 (1)、アメリカ数学会: 83–86、doi :10.2307/2037902、JSTOR  2037902、MR  0291019。
• マルシッチ, ドラガン; Pisanski、Tomaž (2000)、「注目に値する一般化された Petersen グラフG (8,3)」、Math。スロバキア、50 : 117–121、CiteSeerX  10.1.1.28.7183、hdl :10338.dmlcz/133137、MR  1763113、Zbl  0984.05044。
• ウェンディ・ミルボルド、ジェニファー・ウッドコック（2018）「トーラス障害の大規模な集合とその発見方法」、電子ジャーナル・オブ・コンビナトロジー、25（1）：P1.16、doi：10.37236/3797
• ニューフェルド、ユージン、ミルボルド、ウェンディ(1997)、「実用的なトロイダル性テスト」、第 8 回 ACM-SIAM 離散アルゴリズムシンポジウム議事録、pp. 574–580、ISBN 978-0-89871-390-9。
• オルバニッチ、アレン。Pisanski, トマジュ;ランディッチ, ミラノ; Servatius、Brigitte (2004)、「Blanuša double」(PDF)、Math。共通。、9 (1): 91–103、CiteSeerX  10.1.1.361.2772。