頂点グラフ

数学の一分野であるグラフ理論において、頂点グラフとは、単一の頂点を削除することで平面グラフにできるグラフのことである。削除された頂点はグラフの頂点と呼ばれる。頂点グラフは複数の頂点を持つこともあるため、頂点であって頂点ではない。たとえば、極小非平面グラフK ₅またはK _3,3では、すべての頂点が頂点である。頂点グラフには、それ自体が平面であるグラフも含まれ、この場合もすべての頂点が頂点である。ヌルグラフも、削除する頂点がない場合でも頂点グラフとしてカウントされる。

頂点グラフはマイナーを取る操作の下で閉じており、グラフマイナー理論の他のいくつかの側面、すなわちリンクレス埋め込み、^[1]、ハドヴィガーの予想、^[2]、 YΔY-可約グラフ、^[3] 、およびツリー幅とグラフ直径の関係において役割を果たします。^[4]

頂点グラフはマイナーを取る操作の下で閉じている。つまり、任意の辺を縮めるか、任意の辺または頂点を削除すると、別の頂点グラフになる。なぜなら、G が頂点vを持つ頂点グラフである場合、 vを含まない縮めや削除は、 vに関係する辺の削除と同様に、残りのグラフの平面性を維持するからである。vに関係する辺が縮められると、残りのグラフへの影響は、辺のもう一方の端点を削除するのと同等になる。また、v自体が削除されると、他の任意の頂点を頂点として選択できる。^[5]

ロバートソン・シーモア定理によれば、頂点グラフはマイナー閉グラフ族を形成するため、禁制グラフ特性を持つ。頂点グラフでもなく、別の非頂点グラフをマイナーとして持たないグラフは有限個しかない。これらのグラフは、頂点グラフであるという性質上、禁制マイナーである。その他のグラフGが頂点グラフである場合、かつその場合に限り、禁制マイナーのいずれもGのマイナーではない。これらの禁制マイナーには、ピーターセン族の 7 つのグラフ、 K ₅とK _3,3の 2 つの非結合和から形成される 3 つの不連続グラフ、および他の多くのグラフが含まれる。しかし、それらの完全な記述は未だ不明である。^{[5] [6]}

禁制のマイナーの完全な集合は未知であるが、与えられたグラフが頂点グラフであるかどうかをテストし、頂点であればグラフの頂点を線形時間で見つけることは可能である。より一般的には、任意の固定定数kに対して、 k頂点グラフ、つまり最大k 個の頂点の慎重に選択された集合を除去すると平面グラフになるグラフを線形時間で認識することができる。 ^{[7]ただし、} kが可変である場合、問題はNP 完全である。^[8]

すべての頂点グラフの彩色数は最大で 5 です。つまり、 4 色定理により、基礎となる平面グラフには最大で 4 色が必要であり、残りの頂点には最大で 1 色の追加色が必要です。Robertson、Seymour、Thomas (1993a) は、この事実をHadwiger 予想のk = 6の場合の証明、つまりすべての 6 彩色グラフには完全グラフK ₆がマイナーとして存在するという主張の証明に使用しました。彼らは、この予想に対する最小の反例は頂点グラフでなければならないが、6 彩色頂点グラフが存在しないため、そのような反例は存在できないことを示しまし た。

Jørgensen (1994) は、 K _{6 を}マイナーとして持たない6 頂点連結グラフはすべて頂点グラフでなければならないと予想しました。これが証明されれば、Hadwiger 予想に関する Robertson-Seymour-Thomas の結果が直ちに帰結するでしょう。^[2] Jørgensen の予想は未証明のままです。^[9]しかし、もしそれが偽であれば、反例は有限個しかありません。^[10]

グラフ族Fが局所木幅を制限しているとは、 F内のグラフが直径と木幅の間の関数関係に従う場合を言う。つまり、関数fが存在し、 F内の直径d のグラフの木幅は最大でもf ( d )である。頂点グラフは局所木幅を制限しない。n × n のグリッドグラフの各頂点に頂点を接続することによって形成される頂点グラフは木幅がnで直径が 2 であるため、これらのグラフでは木幅は直径の関数によって制限されない。しかし、頂点グラフは局所木幅を制限されると密接に関係している。局所木幅を制限されるマイナー閉グラフ族Fは、まさに頂点グラフを禁制マイナーの 1 つとして持つ族である。^{[4]頂点グラフを禁制マイナーの 1 つとして持つマイナー閉グラフ族は}、頂点マイナーフリーとして知られている。この用語を使用すると、頂点グラフとローカル ツリー幅の関係は、頂点マイナーフリー グラフ ファミリが、制限されたローカル ツリー幅を持つマイナー クローズ グラフ ファミリと同じであるという事実として言い換えることができます。

有界局所木幅の概念は二次元性理論の基礎を形成し、頂点マイナーフリーグラフ上の多くのアルゴリズム問題を多項式時間アルゴリズムまたは固定パラメータの扱いやすいアルゴリズムで正確に解くこと、または多項式時間近似スキームを使用して近似することを可能にします。^{[11]頂点マイナーフリーグラフ族は}グラフ構造定理の強化版に従い、グラフカラーリングと巡回セールスマン問題に対する追加の近似アルゴリズムにつながります。^[12]ただし、これらの結果の一部は、頂点マイナーフリーグラフに関連付ける構造定理を介して、任意のマイナー閉グラフ族に拡張することもできます。^[13]

G が頂点vを持つ頂点グラフであり、τ がG \ { v }の平面埋め込みでvのすべての隣接面をカバーするために必要な最小の面数である場合、 Gは種数τ – 1の 2 次元表面に埋め込むことができます。つまり、平面埋め込みにその数のブリッジを追加し、 v が接続される必要があるすべての面を接続するだけです。たとえば、外平面グラフ( τ = 1のグラフ) に単一の頂点を追加すると、平面グラフが生成されます。G \ { v }が 3 連結の場合、その境界は最適値の定数倍以内です。つまり、G のすべての表面埋め込みには、少なくとも種数⁠ が必要です。 τ/160しかし、頂点グラフの表面埋め込みの最適な種数を決定することはNP困難である。 ^[14]

SPQR木を使用して頂点グラフの平面部分の可能な埋め込みをエンコードすることにより、交差が頂点のみに関係する平面上のグラフの描画を多項式時間で計算し、交差の総数を最小化することが可能になる。 ^[15]しかし、任意の交差が許される場合、平面グラフに単一の辺を追加して形成される頂点グラフの特殊なケースであっても、交差の数を最小化することはNP困難になる。^[16]

頂点グラフは、3次元空間にリンクなしで埋め込み可能で、グラフ内の各サイクルが、グラフの他の特徴によって交差されない円の境界になるように埋め込むことができます。 ^[17]このタイプの描画は、グラフの平面部分を平面に描き、頂点を平面の上に配置し、頂点を各隣接グラフと直線のエッジで接続することによって取得できます。リンクなしで埋め込み可能なグラフは、ピーターセン族の7つのグラフを最小の禁止マイナーとしてマイナー閉族を形成します。^[1]したがって、これらのグラフは頂点グラフのマイナーとしても禁止されています。ただし、頂点グラフではないリンクなしで埋め込み可能なグラフも存在します。

連結グラフは、一連のステップ（ Δ-YまたはY-Δ変換、自己ループまたは多重隣接の削除、1つの隣接頂点の削除、次数2の頂点とその2つの隣接辺を1つの辺に置き換える）によって単一の頂点に削減できる場合、YΔY削減可能である。 ^[3]

頂点グラフやリンクレス埋め込み可能グラフと同様に、YΔY 簡約可能グラフはグラフマイナーの下で閉じています。また、リンクレス埋め込み可能グラフと同様に、YΔY 簡約可能グラフにはピーターセン族の 7 つのグラフが禁制マイナーとして含まれているため、これらが唯一の禁制マイナーであるのか、YΔY 簡約可能グラフはリンクレス埋め込み可能グラフと同じなのかという疑問が生じます。しかし、ニール・ロバートソンは YΔY 簡約可能ではない頂点グラフの例を示しました。すべての頂点グラフはリンクレス埋め込み可能であるため、これはリンクレス埋め込み可能だが YΔY 簡約可能ではないグラフが存在することを示し、したがって YΔY 簡約可能グラフには追加の禁制マイナーが存在することを示しています。^[3]

ロバートソンの頂点グラフは図に示されている。これは、菱形十二面体の3次頂点のそれぞれに頂点を接続するか、4次元超立方体グラフの正反対の頂点を結合することによって得られる。菱形十二面体のグラフは平面であるため、ロバートソンのグラフは頂点グラフである。これは最小次数が4の三角形のないグラフであるため、YΔY縮小によって変更することはできません。^[3]

グラフが頂点グラフである場合、必ずしも唯一の頂点を持つとは限らない。例えば、マイナー極小非平面グラフK ₅とK _3,3では、どの頂点も頂点として選ぶことができる。Wagner (1967, 1970) は、すべての頂点がグラフの頂点になり得るという特性を持つ非平面頂点グラフをほぼ平面グラフと定義した。したがって、 K ₅とK _{3,3 は}ほぼ平面である。彼はこれらのグラフを 4 つのサブセットに分類し、その 1 つは (メビウスの梯子のように)メビウスの帯に、帯の 1 つの辺がグラフのハミルトン閉路と一致するように埋め込むことができるグラフから構成される。四色定理の証明に先立ち、彼は、ほぼ平面グラフはすべて最大で4色で色付けできることを証明した。ただし、ハブ頂点を隣接する2つの頂点に置き換えることで奇数の外部サイクルを持つホイールグラフから形成されるグラフは例外で​​、この場合は5色が必要となる。さらに、彼は、1つの例外（立方体の8頂点補グラフ）を除いて、ほぼ平面グラフはすべて射影平面への埋め込みを持つことを証明した。

しかし、「ほぼ平面グラフ」という語句は非常に曖昧です。頂点グラフ^[18]、平面グラフに1つの辺を追加して形成されたグラフ^[19]、平面埋め込みグラフから、制限された数の面を制限されたパス幅の「渦」に置き換えることによって形成されたグラフ^[20]、およびその他のあまり正確に定義されていないグラフのセットを指すためにも使用されています。

抽象グラフは、n個以下の頂点を削除することで平面グラフにできる場合、n 頂点であると言われます。1 頂点のグラフも頂点であると言われます。

Lipton ら (2018) によると、グラフを平面にするために削除できるエッジがグラフ内に存在する場合、そのグラフはエッジ頂点グラフです。グラフを平面にするために縮小できるエッジがグラフ内に存在する場合、その グラフは縮小頂点グラフです。

一般に、X がグラフのクラスである場合、「頂点-X 」グラフは、頂点を 1 つ削除することでクラスXに含めることができるグラフです。たとえば、頂点-コグラフは、 G―vがコグラフである ような頂点vを持つグラフGです。

• 多面体ピラミッドは、頂点と辺が頂点グラフを形成し、頂点が多面体グラフのすべての頂点に隣接する4次元多面体です。