閾値グラフ

グラフ理論において、閾値グラフとは、1つの頂点を持つグラフから、以下の2つの操作を繰り返し適用することによって構築できるグラフのことである。

1. グラフに単一の孤立した頂点を追加する。
2. グラフに単一の支配頂点、つまり他のすべての頂点に接続されている単一の頂点を追加する。

例えば、図のグラフは閾値グラフです。これは、単一頂点グラフ（頂点1）から始めて、番号順に黒い頂点を孤立頂点として、赤い頂点を支配頂点として追加することで構築できます。

閾値グラフは、 Chvátal & Hammer (1977)によって初めて導入されました。Golumbic (1980)には閾値グラフに関する章があり、 Mahadev & Peled (1995) の書籍は閾値グラフに特化しています。

同等の定義は次のとおりです。グラフが閾値グラフであるとは、実数が存在する場合です。${\displaystyle S}$そして各頂点について${\displaystyle v}$実際の頂点重み${\displaystyle w(v)}$任意の2つの頂点に対して${\displaystyle v,u}$、${\displaystyle uv}$エッジであるのは、${\displaystyle w(u)+w(v)>S}$。

別の同等の定義は次のとおりです。グラフが閾値グラフであるとは、実数が存在する場合です。${\displaystyle T}$そして各頂点について${\displaystyle v}$実際の頂点重み${\displaystyle a(v)}$任意の頂点集合に対して${\displaystyle X\subseteq V}$、${\displaystyle X}$独立であるのは、$\displaystyle \sum _{v\in X}a(v)\leq T.}$

「閾値グラフ」という名称は、以下の定義に由来します。Sはエッジであるという性質の「閾値」であり、あるいは同等にTは独立であるという性質の閾値です。

閾値グラフには禁止グラフ特性もあります。グラフが閾値グラフであるのは、その頂点の 4 つが3 エッジパスグラフ、4 エッジサイクルグラフ、または 2 エッジマッチングである誘導部分グラフを形成しない場合のみです。

頂点の繰り返し追加を用いる定義から、記号列を用いて閾値グラフを一意に記述する別の方法を導き出すことができる。${\displaystyle \epsilon }$は常に文字列の最初の文字であり、グラフの最初の頂点を表します。それ以降の文字はすべて です。${\displaystyle u}$これは、孤立した頂点（または結合頂点）の追加を表します。${\displaystyle j}$これは、支配頂点（または結合頂点）の追加を表します。たとえば、文字列${\displaystyle \epsilon uuj}$は3つの葉を持つ星型グラフを表し、${\displaystyle \epsilon uj}$は3つの頂点上の経路を表します。図のグラフは次のように表すことができます。${\displaystyle \epsilon uuujuuj}$

閾値グラフは、コグラフ、分割グラフ、および自明に完全なグラフの特殊なケースです。グラフが閾値グラフであるのは、それがコグラフかつ分割グラフである場合のみです。自明に完全なグラフであり、かつ自明に完全なグラフの補グラフであるグラフはすべて閾値グラフです。閾値グラフは、区間グラフの特殊なケースでもあります。これらの関係はすべて、禁止された誘導部分グラフによる特徴付けによって説明できます。コグラフは、4 つの頂点 P _{4上に誘導パスがないグラフであり、閾値グラフは、誘導 P 4}、C ₄および 2K ₂がないグラフです。C ₄は 4 つの頂点のサイクルであり、2K ₂はその補グラフ、つまり 2 つの互いに素な辺です。これは、閾値グラフが補グラフを取ることに関して閉じている理由も説明しています。 P ₄は自己相補的であるため、グラフが P ₄、C ₄、および 2K ₂を含まない場合、その補グラフも同様です。

Heggernes & Kratsch (2007)は、閾値グラフは線形時間で認識できることを示しました。グラフが閾値でない場合、障害物 (P ₄、C ₄、または 2K ₂のいずれか) が出力されます。

• 無差別曲線
• 直並列グラフ
• 閾値ハイパーグラフ^{[ 1 ]}

• Chvátal, Václav ; Hammer, Peter L. (1977)、「整数計画法における不等式の集約」、Hammer, PL; Johnson, EL; Korte, BH; 他 編、『整数計画法の研究（1975年ボンワークショップ議事録）』、離散数学年報、第 1巻、アムステルダム：North-Holland、pp. 145–162 。
• ゴルンビック、マーティン・チャールズ（1980）、『アルゴリズム的グラフ理論と完全グラフ』、ニューヨーク：アカデミック・プレス第2版​​、Annals of Discrete Mathematics、57、Elsevier、2004年。
• Heggernes, Pinar ; Kratsch, Dieter (2007)、「線形時間認証認識アルゴリズムと禁止誘導部分グラフ」(PDF)、Nordic Journal of Computing、14 ( 1–2 ): 87–108 (2008)、MR 2460558 、 2008年4月24日にオリジナル(PDF)からアーカイブ済み 。
• Mahadev, NVR; Peled, Uri N. (1995), Threshold Graphs and Related Topics , Elsevier。

• 閾値グラフ、グラフクラスとその包含関係に関する情報システム。