サイクルダブルカバー

グラフ理論 数学において、サイクル二重被覆とは、無向グラフ内のサイクルの集合であり、グラフの各辺がちょうど 2 回含まれます。たとえば、任意の多面体グラフでは、グラフを表す凸多面体の面がグラフの二重被覆を提供します。つまり、各辺はちょうど 2 つの面に属します。

すべてのブリッジのないグラフがサイクル二重被覆を持つかどうかは、WT Tutte、^[1]、 Itai and Rodeh、^[2]、 George Szekeres ^[3]、Paul Seymour ^[4]によって提起され、サイクル二重被覆予想として知られる未解決の問題である。この予想はグラフ埋め込みの観点から同等に定式化することができ、その文脈では循環埋め込み予想としても知られている。

サイクル二重被覆予想の通常の定式化は、すべてのブリッジのない無向グラフが、グラフの各辺がちょうど 2 つのサイクルに含まれるようなサイクルの集合を持つかどうかを問うものです。ブリッジはどのサイクルにも属することができないため、グラフがブリッジのないものであるという要件は、そのようなサイクルの集合が存在するための明らかな必要条件です。サイクル二重被覆予想の条件を満たすサイクルの集合は、サイクル二重被覆と呼ばれます。サイクル グラフやブリッジのないサボテン グラフなどの一部のグラフは、同じサイクルを複数回使用することによってのみ被覆できるため、この種の重複はサイクル二重被覆で許可されます。

スナークはブリッジレスグラフの特殊なケースであり、すべての頂点がちょうど3つの接続辺を持つ（つまり、グラフは立方体である）という追加の特性と、グラフの辺を3つの完全なマッチングに分割することができない（つまり、グラフには3辺の色付けがなく、ヴィジングの定理により彩度指数は4である）という特性を持つ。スナークはサイクル二重被覆予想の唯一の難しいケースであることが判明している。この予想がスナークに当てはまるなら、どのグラフにも当てはまる。^[5]

Jaeger (1985) は、サイクル二重被覆予想に対する潜在的な極小反例では、すべての頂点に 3 本以上の接続辺がなければならないと指摘している。なぜなら、接続辺が 1 本だけの頂点はブリッジを形成するのに対し、2 本の辺が頂点に接続されている場合は、それらの辺を縮小してより小さなグラフを形成し、そのより小さなグラフの二重被覆が元のグラフの 1 つに拡張されるようにすることができるからである。一方、頂点vに 4 つ以上の接続辺がある場合、それらの辺のうち 2 本をグラフから削除し、それらの他の 2 つの端点を接続する単一の辺に置き換えることで、結果として得られるグラフのブリッジレス性を維持したまま、それらの辺のうちの 2 本を「分割」することができる。この場合も、結果として得られるグラフの二重被覆は、元のグラフの二重被覆に簡単に拡張できる。分割されたグラフのすべてのサイクルは、元のグラフのサイクル、またはvで出会う 2 つのサイクルのいずれかに対応する。したがって、すべての極小反例は 3 次でなければならない。しかし、立方体グラフの辺を3色にできる場合（赤、青、緑の3色とすると）、赤と青の辺のサブグラフ、青と緑の辺のサブグラフ、赤と緑の辺のサブグラフはそれぞれ、グラフのすべての辺を2回カバーする分離したサイクルのコレクションを形成します。したがって、すべての最小反例は、3辺に色付けできないブリッジのない立方体グラフ、つまりスナークでなければなりません。^[5]

サイクル二重被覆問題に対する 1 つの可能な攻撃法は、任意のグラフに縮小可能な構成、つまりサイクル二重被覆の有無を維持する方法でより小さな部分グラフに置き換えることができる部分グラフが含まれていることを証明することによって、最小の反例は存在しないことを示すことである。たとえば、立方体グラフに三角形が含まれている場合、Δ-Y 変換により三角形が 1 つの頂点に置き換えられます。より小さなグラフのサイクル二重被覆は、元の立方体グラフのサイクル二重被覆まで拡張できます。したがって、サイクル二重被覆予想に対する最小の反例は三角形のないグラフでなければならず、三角形を含むTietze のグラフなどの一部のスナークは除外されます。コンピューター検索により、立方体グラフの長さが 11 以下のすべてのサイクルは縮小可能な構成を形成することがわかっているため、サイクル二重被覆予想に対する最小の反例は内周が少なくとも12である必要があります。 ^[6]

残念ながら、有限集合の簡約構成を使用してサイクル二重被覆予想を証明することはできません。すべての簡約構成にはサイクルが含まれているため、すべての有限集合Sの簡約構成には、集合内のすべての構成に長さが最大で γ のサイクルが含まれるような数 γ が存在します。ただし、任意の高い内周を持つスナーク、つまり最短サイクルの長さの上限が任意の高さのスナークが存在します。^[7]内周が γ より大きいスナークGには、集合S内のどの構成も含めることができないため、 Sの簡約は、 G が最小の反例である可能性を排除するのに十分強力ではありません。

グラフがサイクル二重被覆を持つ場合、被覆のサイクルは、2次元セル複合体へのグラフ埋め込みの2セルを形成するために使用できます。立方体グラフの場合、この複合体は常に多様体を形成します。グラフは、埋め込みのすべての面がグラフ内の単純サイクルである点で、多様体上に循環的に埋め込まれていると言われています。ただし、次数が3を超えるグラフのサイクル二重被覆は、多様体上の埋め込みに対応しない場合があります。被覆のサイクルによって形成されるセル複合体は、その頂点に非多様体トポロジを持つ場合があります。循環埋め込み予想または強い埋め込み予想^{[5]は、すべての}2頂点接続グラフは多様体への循環埋め込みを持つと述べています。そうである場合、グラフには、埋め込みの面によって形成されるサイクル二重被覆もあります。

立方体グラフの場合、2頂点連結性とブリッジレス性は同等である。したがって、円形埋め込み予想は明らかにサイクル二重被覆予想と少なくとも同程度に強力である。^[5]

円形埋め込みが存在する場合、それは最小種数の面上にはない可能性がある。Nguyen Huy Xuongは、円形埋め込みがトーラス上に存在しない2頂点連結トーラスグラフを説明した。 ^[5]

円形埋め込み予想のより強力なバージョンとして、2頂点連結グラフはすべて有向多様体上に円形埋め込みを持つという予想も考えられている。サイクル二重被覆予想の観点から見ると、これは、サイクル二重被覆と、被覆内の各サイクルの向きが存在し、すべての辺eについて、eを覆う2つのサイクルがeを通して反対方向に向いているという予想と同等である。^[5]

あるいは、被覆内のサイクルの色付けを含む予想の強化も検討されている。これらの中で最も強力なのは、すべてのブリッジレスグラフは、面を5色にすることができる向き付け可能な多様体上に円形の埋め込みを持つという予想である。これが真実であれば、すべてのブリッジレスグラフにはどこにもゼロのない5フローがあるというWT Tutteの予想が成立することになる。^[5]

円形埋め込みよりも強力な埋め込みの種類は、多面体埋め込みです。これは、すべての面が単純閉路であり、交差するすべての 2 つの面が単一の頂点または単一の辺で交差するような方法でグラフを表面に埋め込むものです。(立方体グラフの場合、これは、交差するすべての 2 つの面が単一の辺で交差するという要件に簡略化できます。) したがって、閉路二重被覆予想がスナークに還元されることを考えると、スナークの多面体埋め込みを調査することは興味深いことです。そのような埋め込みを見つけることができなかったため、Branko Grünbaum は存在しないと予想しましたが、Kochol (2009a、2009b) は多面体埋め込みを持つスナークを見つけることで Grünbaum の予想を反証しました。

• ピーターセン彩色予想

• 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、S2CID  118767538。
• Itai, A.; Rodeh, M. (1978)、「回路によるグラフのカバー」、オートマトン、言語、プログラミング。ICALP 1978。、コンピュータサイエンスの講義ノート (Ausiello, G.、Böhm, C. (編))、第 62 巻、Springer、pp. 289–299、doi :10.1007/3-540-08860-1_21、ISBN 978-3-540-08860-8{{citation}}: CS1 メンテナンス: 日付と年 (リンク)。
• ハック、A.（2000）、「サイクル二重被覆予想の縮小可能な構成」、離散応用数学、99（1–3）：71–90、doi：10.1016 / S0166-218X（99）00126-2。
• Jaeger, F. (1985)、「サイクル二重被覆予想の調査」、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、ISBN 978-0-444-87803-8。
• ココル、マーティン (1996)、「小さなサイクルのないスナーク」、組み合わせ理論ジャーナル、シリーズ B、67 (1) (第 1 版): 34–47、doi : 10.1006/jctb.1996.0032。
• Kochol, Martin (2009a)、「3 辺が着色可能でない 3 正則グラフと有向面への多面体埋め込み」、Graph Drawing 2008、編集者: IG Tollis、M. Patrignani、Lecture Notes in Computer Science、vol. 5417、pp. 319–323。
• ココル、マーティン (2009b)、「有向面におけるスナークの多面体埋め込み」、アメリカ数学会紀要、137 (5) (第 5 版): 1613–1619、doi : 10.1090/S0002-9939-08-09698-6。
• シーモア、PD（1979）、「回路の合計」、ボンディ、JA、マーティ、USR（編）、グラフ理論と関連トピック、ニューヨーク：アカデミックプレス、pp. 342-355、ISBN 978-0121143503{{citation}}: CS1 メンテナンス: 日付と年 (リンク)。
• Szekeres, G. (1973)、「立方グラフの多面体分解」、オーストラリア数学会誌、8 (3): 367–387、doi : 10.1017/S0004972700042660。
• Tutte, WT (1987)、H. Fleischner との個人的な書簡 (1987 年 7 月 22 日)。
• 張 存全 (1997)、「グラフの整数フローとサイクルカバー」、CRC Press、ISBN 978-0-8247-9790-4。
• 張 存全 (2012)、Circuit Double Cover of Graphs、ケンブリッジ大学出版局、ISBN 978-0-5212-8235-2。

• Open Problem Garden からの、サイクル二重被覆予想、円形埋め込み予想、および Grünbaum 予想。
• サイクル二重被覆予想は、Wayback Machineで 2008-12-05 にアーカイブされています。Dan Archdeacon。
• ワイスシュタイン、エリック W.、「サイクル二重被覆予想」、MathWorld