境界グラフ

グラフ理論において、境界グラフは、ある半順序集合のどの要素のペアが上限を持つかを表します。厳密には、任意のグラフGは、 Gの頂点上に半順序 ≤ が存在し、Gの任意の頂点uとvに対して、uv がGの辺であるのはu ≠ vの場合のみであり、 u ≤ wかつv ≤ wとなる頂点wが存在する場合、境界グラフです。^{[ 1 ]}

束縛グラフとは、クリーク辺被覆を持つグラフのことです。クリーク辺被覆とは、すべての辺を覆うクリークの族であり、さらに各クリークには、その族内の他のどのクリークにも属さない頂点が含まれるという性質を持ちます。このようにクリークで覆われたグラフは、各クリーク内の一意の頂点を鎖状に並べ、そのクリーク内の他のすべての頂点の上に並べることで得られる、頂点上の部分順序の束縛グラフです。^{[ 1 ]}

与えられた部分順序の境界グラフの場合、各クリークは、ある特定の要素以下の要素のサブセットとみなすことができます。この被覆は、与えられた順序の線形拡張とともに、順序付きエッジ被覆を生成します。これは、各頂点が持つ特性を持つ頂点上の全順序とエッジクリーク被覆を組み合わせたものです。${\displaystyle v_{i}}$は、カバー内の 1 つのクリークの唯一の頂点であり (おそらくそれだけで構成されており)、他のすべての頂点は${\displaystyle v_{j}}$仲間内で${\displaystyle v_{i}}$より後に現れる${\displaystyle v_{i}}$順序付けにおいて、そして${\displaystyle v_{j}}$の仲間の中に現れる${\displaystyle v_{i}}$の仲間${\displaystyle v_{j}}$は、クリークのサブセットです。${\displaystyle v_{i}}$[ ^{2 ]​}

境界グラフは、上限グラフと呼ばれることもありますが、^{[ 3 ]}同様に定義された下限グラフもまったく同じクラスを構成します。≤ の任意の下限は、双対部分順序 ≥の上限であることが容易にわかります。

グラフは、各辺が単体頂点の閉近傍に属する場合に限り、束縛グラフである。これらの単体頂点は、基となる半順序の最大要素に対応する。この特徴付けにより、束縛グラフを多項式時間で認識することができる。^{[ 3 ]}

• Tanenbaum, PJ (2000). "Bound graph polysemy" (PDF) . Electronic Journal of Combinatorics . 7 R43: #R43. doi : 10.37236/1521 .