二分半分

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

例

例えば、完全二部グラフ $K n, n$ の二部半分は完全グラフ $K n$ であり、超立方体グラフの二部半分は半立方体グラフである。G $が$ 距離正則グラフである場合、その 2 つの二部半分は両方とも距離正則である。^[2]例えば、半フォスターグラフは有限個の次数 6 の距離正則局所線型グラフの 1 つである。^[3]

表現と硬さ

あらゆるグラフ $G$ は、別のグラフの二部グラフであり、 $G$ の辺を2 辺のパスに分割することによって形成されます。より一般的には、 $Gの二部グラフとしての表現は、$ $G$ の任意のクリーク辺被覆を取り、各クリークを星に置き換えることによって見つけることができます。^{[4]すべての表現はこのようにして生じます。最小のクリーク辺被覆を見つけることは NP 困難であるため、} $G$ が二部グラフである頂点が最も少ないグラフを見つけることも困難です。 ^[5]

特別なケース

マップグラフ、つまり平面内の内部分離単連結領域の交差グラフは、まさに二部平面グラフの二部半分である。^[6]

参照

二部二重カバー

参考文献

^ ウィルソン、ロビン J. (2004)、代数グラフ理論のトピック、数学とその応用百科事典、第 102 巻、ケンブリッジ大学出版局、p. 188、ISBN 9780521801973。
^ 千原, ローラ; スタントン, デニス (1986)、「直交多項式の連想スキームと二次変換」、グラフと組合せ論、2 (2): 101–112、doi :10.1007/BF01788084、MR 0932118、S2CID 28803214。
^ 平木明; 野村一正; 鈴木博 (2000)、「価数 6 およびの距離正則グラフ」、代数組合せ論ジャーナル、11 (2): 101–134、doi : 10.1023/A:1008776031839、MR 1761910 $a_{1}=1$
^ Le、Hoàng-Oanh; 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 巻、ケンブリッジ大学出版局、p. 188、ISBN 9780521801973。

[2] 千原, ローラ; スタントン, デニス (1986)、「直交多項式の連想スキームと二次変換」、グラフと組合せ論、2 (2): 101–112、doi :10.1007/BF01788084、MR 0932118、S2CID 28803214。

[3] 平木明; 野村一正; 鈴木博 (2000)、「価数 6 およびの距離正則グラフ」、代数組合せ論ジャーナル、11 (2): 101–134、doi : 10.1023/A:1008776031839、MR 1761910 $a_{1}=1$

[4] Le、Hoàng-Oanh; 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。