距離遺伝グラフ

離散数学の一分野であるグラフ理論において、距離継承グラフ（完全分離グラフとも呼ばれる）^{[ 1 ]}は、任意の連結誘導部分グラフ内の距離が元のグラフ内の距離と同じであるグラフである。したがって、任意の誘導部分グラフは、より大きなグラフの距離を継承する。

距離遺伝グラフはHoworka（1977）によって命名され、最初に研究されたが、同等のグラフのクラスは1970年にOlariuとSachsによって既に完全であることが示されていた。^{[ 2 ]}

距離遺伝グラフがグラフの交差クラスを構成することは以前から知られていたが、^{[ 3 ]} Gioan & Paul (2012)によって提示されるまで交差モデルは知られていなかった。

距離遺伝グラフの本来の定義は、任意の2つの頂点uとvがGの連結誘導部分グラフHに属する場合、G内のuとvを結ぶ最短経路がHの部分グラフでなければならず、 H内のuとv間の距離がG内の距離と同じになるようなグラフGである。

距離遺伝グラフは、他にもいくつかの同等の方法で特徴付けることができます。^{[ 4 ]}

• これらは、誘導経路がすべて最短経路であるグラフ、あるいは同等に、最短経路でないすべての経路において、連続しない2つの経路頂点を結ぶ辺が少なくとも1つ存在するグラフである。
• これらは、長さが5以上のすべてのサイクルにおいて、少なくとも2本の交差する対角線が存在するグラフである。
• これらは、任意の 4 つの頂点u、v、w、およびxに対して、距離の 3 つの合計d ( u、v ) + d ( w、x )、d ( u、w ) + d ( v、x )、およびd ( u、x ) + d ( v、w )のうち少なくとも 2 つが互いに等しいグラフです。
• これらは、等長部分グラフとして長さが5以上のサイクル、または他の3つのグラフ（1つの弦を持つ5サイクル、交差しない2つの弦を持つ5サイクル、対向する頂点を結ぶ弦を持つ6サイクル）のいずれも持たないグラフである。

• これらは、図に示すように、単一の頂点から次の3つの操作を連続して行うことで構築できるグラフです。
  1. グラフの既存の頂点に、1本の辺で接続された新しい垂下頂点を追加します。
  2. グラフの任意の頂点を、それぞれが置換された頂点と同じ隣接頂点の集合を持つ2つの頂点のペアに置き換える。この新しい2つの頂点のペアは、互いに偽の双子と呼ばれる。
  3. グラフの任意の頂点を、それぞれが置換された頂点の隣接頂点と、もう一方の頂点を隣接頂点とする2つの頂点のペアに置き換える。この新しい2つの頂点のペアは、互いに真の双子と呼ばれる。
• これらは、分割分解によってクリークとスター（完全二部グラフK _{1, q}）に完全に分解できるグラフです。この分解では、グラフを 2 つのサブセットに分割し、その 2 つのサブセットを分離するエッジが完全二部部分グラフを形成し、分割の 2 つの側をそれぞれ単一の頂点に置き換えることによって 2 つのより小さなグラフを形成し、これらの 2 つの部分グラフを再帰的に分割します。^{[ 5 ]}
• これらはまさにランク幅が最大で１のグラフであり、グラフのランク幅は、グラフの頂点のすべての階層的分割において、その分割によって決定されるグラフの隣接行列の特定のサブ行列の中での最大ランクの最小値として定義される。^{[ 6 ]}
• これらはHHDGフリーグラフであり、誘導部分グラフがハウス（ 5頂点パスグラフの補グラフ）、ホール（ 5つ以上の頂点を持つサイクルグラフ）、ドミノ（6頂点サイクルと対向する2つの頂点間の対角線エッジ）、またはジェム（5頂点サイクルと、同じ頂点に接続する2つの対角線）にならないという禁止グラフ特性を持つことを意味します。

すべての距離遺伝グラフは完全グラフであり、^{[ 7 ]}より具体的には完全順序付け可能グラフ^{[ 8 ]}およびメイニエルグラフです。すべての距離遺伝グラフはパリティグラフでもあり、同じ頂点のペア間の誘導パスの任意の 2 つが両方とも奇数の長さであるか、両方とも偶数の長さであるグラフです。^{[ 9 ]}距離遺伝グラフGの任意の偶数乗(つまり、G内の距離が最大2 iの頂点のペアを接続して形成されるグラフG ^{2 i} ) は弦グラフです。^{[ 10 ]}

距離継承グラフはすべて、円上の弦の交差グラフとして表現でき、円グラフを形成します。これは、グラフに垂下頂点、偽の双子、および真の双子を追加して構築することで確認できます。各ステップで、グラフを表す対応する弦のセットが構築されます。垂下頂点を追加することは、既存の弦の端点の近くに弦を追加して、その弦のみと交差するようにすることに対応します。偽の双子を追加することは、同じ他の弦のセットと交差する 2 つの平行な弦で弦を置き換えることに対応します。真の双子を追加することは、互いに交差するがほぼ平行で、同じ他の弦のセットと交差する 2 つの弦で弦を置き換えることに対応します。

距離遺伝グラフは、三角形を含まない場合に限り二部グラフである。二部距離遺伝グラフは、真の双子は三角形を形成するが、垂下頂点と偽の双子の操作によって二部性が維持されるため、単一の頂点から垂下頂点と偽の双子のみを追加することによって構築できる。すべての二部距離遺伝グラフは弦二部グラフであり、モジュラーである。^{[ 11 ]}

1 つの頂点から、偽の双子操作なしに、垂下頂点と真の双子によって構築できるグラフは、プトレマイオス グラフの特殊なケースであり、ブロック グラフが含まれます。 1 つの頂点から、垂下頂点なしに、偽の双子操作と真の双子操作によって構築できるグラフは、コグラフであり、したがって距離遺伝的です。コグラフは、直径 2 の距離遺伝的グラフの互いに素な和集合です。距離遺伝的グラフの任意の頂点の近傍はコグラフです。任意の木の辺の任意の向きのセットを選択して形成される有向グラフの推移閉包は距離遺伝的です。木が何らかの頂点から一貫して離れるように向き付けられている特殊なケースは、自明に完全なグラフとして知られる距離遺伝的グラフのサブクラスを形成し、これは弦コグラフとも呼ばれます。^{[ 12 ]}

距離遺伝グラフは線形時間で認識され、ペンダント頂点とツイン操作のシーケンスに解析される。^{[ 13 ]}

距離継承グラフは完全グラフであるため、 より一般的なグラフクラスではNP困難である最適化問題の一部は、距離継承グラフでは多項式時間で解くことができます。したがって、距離継承グラフでは最大クリークまたは最大独立集合を多項式時間で見つけることができ、任意の距離継承グラフの最適なグラフ彩色を見つけることもできます。 ^{[ 14 ]}距離継承グラフは円グラフ であるため、円グラフの多項式時間アルゴリズムを継承します。たとえば、任意の円グラフ、したがって任意の距離継承グラフの木幅を多項式時間で決定することができます。 ^{[ 15 ]} さらに、任意の距離継承グラフのクリーク幅は最大で3です。^{[ 16 ]}その結果、クールセルの定理により、これらのグラフ上の多くの問題に対して効率的な動的計画法アルゴリズムが存在します。^{[ 17 ]}

距離遺伝グラフ用に特別に設計されたアルゴリズムを使用すると、他のいくつかの最適化問題もより効率的に解決できます。D'Atri & Moscarini (1988) が示すように、距離遺伝グラフでは、最小連結支配集合(または同等に、最大数の葉を持つ全域木) を多項式時間で見つけることができます。任意の距離遺伝グラフのハミルトン閉路またはハミルトン路も多項式時間で見つけることができます。^{[ 18 ]}

• 「距離遺伝グラフ」、グラフクラスとその包含関係に関する情報システム。