二部二重カバー

グラフ理論において、無向グラフGの二部二重被覆は、Gの二部被覆グラフであり、 Gの2 倍の頂点を持つ。これは、グラフのテンソル積G × K ₂として構築できる。これは、クロネッカー二重被覆、標準二重被覆、または単にGの二部二重とも呼ばれる。

これを、各エッジを 2 回含むサイクルの族であるグラフの サイクル二重被覆と混同しないでください。

Gの二部二重被覆には、 Gの各頂点v _iに対して2 つの頂点u _iとw _{i が}あります。2 つの頂点u _iとw _{j が}二重被覆の辺で接続されるのは、v _iとv _jがGで辺で接続されている場合のみです。たとえば、以下は非二部グラフGの二部二重被覆の図です。この図では、テンソル積の各頂点は、積の第 1 項 ( G ) の色と積の第 2 項 ( K ₂ ) の形状を使用して示されています。したがって、二重被覆の頂点u _{i は}円で示され、頂点w _{i は}四角で示されています。

二部二重被覆は、隣接行列（下記参照）を使用して構築することも、Gの各辺が2 要素群の非ゼロ要素でラベル付けされた電圧グラフの導出グラフとして構築することもできます。

ピーターセングラフの二部二重被覆はデザルググラフである：K ₂ × G (5,2) = G (10,3)。

完全グラフ K _nの二部二重被覆はクラウングラフ（完全二部グラフ K _n、nから完全マッチングを引いたもの）である。特に、四面体のグラフK ₄の二部二重被覆は立方体のグラフである。

奇数長サイクルグラフの二部二重被覆は長さが 2 倍のサイクルですが、任意の二部グラフの二部二重被覆 (次の例に示す偶数長サイクルなど) は、元のグラフの互いに素な 2 つのコピーによって形成されます。

無向グラフGが隣接行列として行列Aを持つ場合、 Gの二重被覆の隣接行列は

${\displaystyle \left[{\begin{matrix}0&A\\A^{T}&0\end{matrix}}\right],}$

そして、Gの二重被覆の双隣接行列はAそのものになります。つまり、グラフからその二重被覆への変換は、A を隣接行列ではなく双隣接行列として再解釈するだけで実行できます。より一般的には、有向グラフの隣接行列を双隣接行列として再解釈すると、有向グラフとバランスのとれた二部グラフの組み合わせ的同値性が実現されます。^[1]

任意のグラフGの二部二重被覆は二部グラフである。二部グラフの両方の部分は、 Gの各頂点に対して1つの頂点を持つ。二部二重被覆が連結であるためには、Gが連結かつ非二部である必要がある。^[2]

二部二重被覆は二重被覆（2 重被覆グラフ）の特殊なケースです。グラフ理論における二重被覆は、位相的二重被覆の特殊なケースとして考えることができます。

Gが非二部対称グラフである場合、Gの二重被覆も対称グラフである。この方法で、いくつかの既知の立方体対称グラフが得られる。たとえば、K ₄の二重被覆は立方体のグラフであり、ピーターセングラフの二重被覆はデザルググラフであり、十二面体のグラフの二重被覆は40頂点の対称立方体グラフである。^[3]

2 つの異なるグラフが同型な二部二重被覆を持つことも可能である。例えば、デザルググラフはピーターセングラフの二部二重被覆であるだけでなく、ピーターセングラフと同型ではない別のグラフの二部二重被覆でもある。^[4]すべての二部グラフが別のグラフの二部二重被覆であるとは限らない。二部グラフG が別のグラフの二部被覆となるためには、 Gの自己同型に各頂点を別個の隣接しない頂点に写像する反転が含まれていることが必要かつ十分である。 ^[4]例えば、2 つの頂点と 1 つの辺を持つグラフは二部グラフであるが二部二重被覆ではない。なぜなら、そのような反転によって互いに写像される隣接しない頂点のペアがないからである。一方、立方体のグラフは二部二重被覆であり、各頂点を正反対の頂点にマッピングする反転を持ちます。二部二重被覆構成によって形成される二部グラフの別の特徴付けは、Sampathkumar (1975) によって得られました。

二部ではない連結グラフでは、二部である二重被覆は 1 つだけですが、グラフが二部または非連結である場合は、複数の二重被覆が存在する可能性があります。このため、 Tomaž Pisanski は、「二部二重被覆」という名前は、明確な名前である「標準二重被覆」または「クロネッカー被覆」に置き換えて推奨すべきであると主張しました。^[5]

一般に、グラフは二部二重被覆とは異なる複数の二重被覆を持つことがある。^[6]

1. グラフC がHの被覆グラフであるとは、 CからHへの全射的局所同型f が存在する場合です。図では、全射は色で示されています。たとえば、f はCの両方の青いノードをHの青いノードにマップします。さらに、X をCの青いノードの近傍とし、Y をHの青いノードの近傍とすると、 fのXへの制限はXからYへの全単射です。特に、各青いノードの次数は同じです。同じことが各色にも当てはまります。
2. グラフC は、 H内の各ノードの原像のサイズが 2 の場合、Hの二重カバー(または2 重カバー、あるいは2 リフト)です。この例では、CにはH内の青いノードにマッピングされるノードが2 つあります。

次の図では、グラフC はグラフHの二重被覆です。

しかし、C はHや他のグラフ の二部二重被覆ではなく、二部グラフではありません。

H内の 1 つの三角形を 1 つの正方形に置き換えると、結果のグラフには 4 つの異なる二重被覆が存在します。そのうち 2 つは二部被覆ですが、クロネッカー被覆は 1 つだけです。

別の例として、二十面体のグラフは完全グラフK _{6の二重被覆です。二十面体から}K ₆への被覆写像を得るには、二十面体の反対の頂点の各ペアをK _{6の単一の頂点に写像します。しかし、二十面体は二部ではないので、} K ₆の二部二重被覆ではありません。代わりに、これは射影平面上のK ₆の埋め込みの向き付け可能な二重被覆として得ることができます。

グラフの二重カバーは、グラフの エッジに署名するさまざまな方法に対応します。

• 二分半分

• Brualdi, Richard A.; Harary, Frank ; Miller, Zevi (1980)、「行列によるバイグラフとダイグラフの比較」、Journal of Graph Theory、4 (1): 51–73、doi :10.1002/jgt.3190040107、MR  0558453。
• Dulmage, AL; Mendelsohn, NS (1958)、「二部グラフの被覆」、Canadian Journal of Mathematics、10 : 517–534、doi : 10.4153/CJM-1958-052-0、MR  0097069この論文のタイトルにある「被覆」は頂点被覆問題を指しており、二部二重被覆を指しているわけではない。しかし、Brualdi、Harary、Miller (1980) は、隣接行列を双隣接行列として再解釈するというアイデアの出典としてこの論文を引用している。
• フェン、ヤンクアン。Kutnar, クラウディヤ;マルニッチ、アレクサンダー。マルシッチ、ドラガン(2008)、「グラフの 2 つ折りカバーについて」、Journal of Combinatorial Theory、シリーズ B、98 (2): 324–341、arXiv : math.CO/0701722、doi :10.1016/j.jctb。 2007.07.001、MR  2389602、S2CID  8626473。
• イムリッチ、ウィルフリード、ピサンスキ、トマシュ(2008)、「多重クロネッカー被覆グラフ」、ヨーロッパ組合せ論ジャーナル、29 (5): 1116–1122、arXiv : math/0505135、doi :10.1016/j.ejc.2007.07.001、MR  2419215、S2CID  29878870。
• ピサンスキ、トマシュ(2018)、「すべての二部二重被覆が標準的であるとは限らない」、ICA 紀要、82 : 51–55
• Sampathkumar, E. (1975)、「テンソル積グラフについて」、オーストラリア数学会誌、20 (3): 268–273、doi : 10.1017/S1446788700020619、MR  0389681。
• Waller, Derek A. (1976)、「グラフの二重カバー」(PDF)、オーストラリア数学会誌、14 (2): 233–248、doi : 10.1017/S0004972700025053、hdl :10338.dmlcz/101887、MR  0406876。

• ワイスタイン、エリック W.「二部二重グラフ」。マスワールド。