二分割された半分

次数4の半立方体グラフは、次数4の超立方体グラフの二部グラフの半分として得られる。

グラフ理論では、二部グラフ $G$ $= ($ $U$ $,$ $V$ $,$ $E$ $)$ の二部半分または半正方形は、頂点集合が二分割の 2 つの側のいずれかであるグラフ(一般性を失うことなく、 $U$ ) であり、 $U$ 内の各頂点ペア $u$ $i$ $、$ $u$ $j$ $がG$ 内で互いに距離2 にある場合、辺 $u$ $i$ $u$ $j$ が存在するグラフです。^[¹^]つまり、より簡潔な表記では、二部半分は $G$ $2$ $[$ $U$ $]$ であり、上付き文字 2 はグラフの正方形を表し、角括弧は誘導部分グラフを表します。

例

例えば、完全二部グラフ $K n, n$ の二部半分は完全グラフ $K n$ であり、ハイパーキューブグラフの二部半分は半分キューブグラフです。G $が$ 距離正則グラフの場合、その 2 つの二部半分は両方とも距離正則です。^{[ 2 ]}例えば、半分フォスターグラフは、有限個の次数 6 の距離正則局所線形グラフの 1 つです。^{[ 3 ]}

表現と硬さ

すべてのグラフ $G$ は、別のグラフの二部グラフの半分であり、 $G$ のエッジを 2 つのエッジのパスに分割することによって形成されます。より一般的には、G の任意のクリークエッジカバーを取り、各クリークをスターに置き換えることによって、G の二部グラフの半分としての表現を $見つける$ ことができ $ます$ 。[ 4 ^]^すべて^の $表現はこのようにして生じます。最小のクリークエッジカバーを見つけることが NP 困難であるため、 G$ が二部グラフの半分となる最小の頂点を持つグラフを見つけることも NP 困難です。^[⁵^]

特別なケース

マップグラフ、すなわち平面内の内部的に互いに素な単連結領域の交差グラフは、二部平面グラフの二部半分に正確に一致する。^{[ 6 ]}

参考文献

↑ウィルソン、ロビン J. (2004)、「代数グラフ理論のトピックス」、数学とその応用百科事典、第 102 巻、ケンブリッジ大学出版局、188 ページ、ISBN 9780521801973。
↑ Chihara, Laura; Stanton, Dennis (1986), "直交多項式の結合スキームと二次変換", Graphs and Combinatorics , 2 (2): 101–112 , doi : 10.1007/BF01788084 , MR 0932118 , S2CID 28803214 。
↑平木明、野村和正、鈴木浩（2000）「価数6と $a_{1}=1$ 「, Journal of Algebraic Combinatorics , 11 (2): 101– 134, doi : 10.1023/A:1008776031839 , MR 1761910
↑レ、ホアンオアン; Le、Van Bang (2019)、「マップグラフと半正方形の制約表現」、Rossmanith、Peter;ヘガーネス、ピナール。 Kataen、Joost-Pieter (編)、44th International Symposium on Mathematical Foundations of Computer Science、MFCS 2019、2019 年 8 月 26 ～ 30 日、ドイツ、アーヘン、LIPIcs、vol. 138、Schloss Dagstuhl - Leibniz-Zentrum für Informatik、pp. 13:1–13:15、doi : 10.4230/LIPIcs.MFCS.2019.13、ISBN 9783959771177
↑ゲイリー、マイケル・R. ;ジョンソン、デイビッド・S. (1979).コンピュータと難解性：NP完全性理論への手引き. 数学科学シリーズ（第1版）. ニューヨーク：WHフリーマン社. ISBN 9780716710455. MR 0519066 . OCLC 247570676 . 問題GT59。
↑陳志忠;グリニ、ミケランジェロ。Papadimitriou、Christos H. (2002)、「マップグラフ」、Journal of the ACM、49 (2): 127–138、arXiv : cs/9910013、doi : 10.1145/506147.506148、MR 2147819、S2CID 2657838 。

[1] ウィルソン、ロビン J. (2004)、「代数グラフ理論のトピックス」、数学とその応用百科事典、第 102 巻、ケンブリッジ大学出版局、188 ページ、ISBN 9780521801973。

[2] Chihara, Laura; Stanton, Dennis (1986), "直交多項式の結合スキームと二次変換", Graphs and Combinatorics , 2 (2): 101–112 , doi : 10.1007/BF01788084 , MR 0932118 , S2CID 28803214 。

[3] 平木明、野村和正、鈴木浩（2000）「価数6と $a_{1}=1$ 「, Journal of Algebraic Combinatorics , 11 (2): 101– 134, doi : 10.1023/A:1008776031839 , MR 1761910

[4] レ、ホアンオアン; Le、Van Bang (2019)、「マップグラフと半正方形の制約表現」、Rossmanith、Peter;ヘガーネス、ピナール。 Kataen、Joost-Pieter (編)、44th International Symposium on Mathematical Foundations of Computer Science、MFCS 2019、2019 年 8 月 26 ～ 30 日、ドイツ、アーヘン、LIPIcs、vol. 138、Schloss Dagstuhl - Leibniz-Zentrum für Informatik、pp. 13:1–13:15、doi : 10.4230/LIPIcs.MFCS.2019.13、ISBN 9783959771177

[5] ゲイリー、マイケル・R. ;ジョンソン、デイビッド・S. (1979).コンピュータと難解性：NP完全性理論への手引き. 数学科学シリーズ（第1版）. ニューヨーク：WHフリーマン社. ISBN 9780716710455. MR 0519066 . OCLC 247570676 . 問題GT59。

[6] 陳志忠;グリニ、ミケランジェロ。Papadimitriou、Christos H. (2002)、「マップグラフ」、Journal of the ACM、49 (2): 127–138、arXiv : cs/9910013、doi : 10.1145/506147.506148、MR 2147819、S2CID 2657838 。

[

[ 2 ]

[ 3 ]

]

[

[ 6 ]

例

表現と硬さ

特別なケース

関連項目

参考文献