ピーターセン家

グラフ理論において、ピーターセン族はピーターセングラフと完全グラフ $K$ $6$ を含む7 つの無向グラフの集合です。ピーターセン族は、ピーターセングラフの名前の由来となったデンマークの数学者Julius Petersenにちなんで名付けられました。

ピーターセン族のグラフはどれも、YΔ変換とΔY変換によって族内の他のグラフに変換できます。YΔY変換では、三角形を3次の頂点に置き換えたり、その逆を行ったりします。これらの7つのグラフは、リンクなしで埋め込み可能なグラフの禁制のマイナーを形成します。これは、グラフ内の2つのサイクルがリンクされていない方法で3次元空間に埋め込むことができるグラフです。^{[1]これらは、}YΔY簡約グラフの禁制のマイナーにも含まれています。^[2]^[3]

意味

Petersen ファミリーを定義するために使用される YΔ 変換と ΔY 変換の形式は次のとおりです。

グラフ $G に$ ちょうど 3 つの隣接頂点を持つ頂点 $vが含まれている場合、$ $v$ における $G$ の YΔ 変換は、 $G$ から $v を$ 削除し、その 3 つの隣接頂点の各ペア間に辺を追加することによって形成されるグラフです。
グラフ $H$ に三角形 $uvw が含まれている場合、$ $uvw$ における $H$ の ΔY 変換は、 $H$ から辺 $uv$ 、 $vw$ 、 $uwを削除し、$ $u$ 、 $v$ 、 $w$ の 3 つすべてに接続された新しい頂点を追加することによって形成されるグラフです。

これらの変換は、グラフ内の三角形が Δ 形状で、次数 3 の頂点が Y 形状であることからこのように呼ばれています。これらの操作は原理的にはマルチグラフにつながりますが、ピーターセン族内では発生しません。これらの操作はグラフ内の辺の数を保存するため、ΔY 変換と YΔ 変換の組み合わせによって単一の開始グラフ $G$ から形成できるグラフまたはマルチグラフは有限個しかありません。

ピーターセン族は、ΔY 変換と YΔ 変換の組み合わせによってピーターセングラフから到達できるすべてのグラフで構成されます。この族には、6 つの頂点を持つ完全グラフ $K 6$ 、完全二部グラフ $K 4,4$ から 1 つの辺を削除して形成される 8 頂点グラフ、および 7 つの頂点を持つ完全三部グラフ $K 3,3,1$ の7 つのグラフが含まれます。

未成年者の立ち入り禁止

グラフGのマイナーグラフは、 Gから辺を縮小および削除することで形成される別のグラフです。ロバートソン・シーモア定理が示すように、多くの重要なグラフ族は、禁制マイナーグラフの有限集合によって特徴付けることができます。たとえば、ワグナーの定理によれば、平面グラフは、完全グラフK ₅も完全二部グラフK _3,3もマイナーグラフとして持たないグラフです。

ニール・ロバートソン、ポール・シーモア、ロビン・トーマスは、グラフのリンクレス埋め込みの同様の特徴付けの一部としてピーターセン族を使用しました。リンクレス埋め込みとは、グラフのすべてのサイクルがグラフの他の部分が交差しないディスクの境界であるような方法での、与えられたグラフのユークリッド空間への埋め込みです。 ^[1]ホルスト・ザックスは以前にそのような埋め込みを研究し、ピーターセン族の7つのグラフにはそのような埋め込みがないことを示し、リンクレス埋め込み可能なグラフを禁制サブグラフで特徴付けるという問題を提起しました。^[4]ロバートソンらは、リンクレス埋め込み可能グラフはピーターセン族のメンバーをマイナーとして持たないグラフとまったく同じであることを示し、サックスの問題を解決しました。

ピーターセン族は、別のグラフ族である YΔY 簡約グラフの禁制マイナーの一部も形成します。連結グラフが YΔY 簡約可能であるとは、一連の手順 (各手順は ΔY または YΔ 変換、自己ループまたは多重隣接の削除、1 つの隣接頂点の削除、次数 2 の頂点とその 2 つの隣接辺を単一の辺に置き換える) によって単一の頂点に簡約できる場合です。たとえば、完全グラフ K 4 は、YΔ_{変換(2 重の辺を持つ三角形に変換)、3 つの重複辺の削除、ΔY 変換 (}クロー K _1,3に変換) 、クローの次数 1 の 3 つの頂点の削除によって、単一の頂点に簡約できます。ピーターセン族のグラフはそれぞれ、YΔY 簡約グラフ族の最小禁制マイナーを形成します。^[2]しかし、ニール・ロバートソンは、 YΔY-還元可能ではない頂点グラフ（平面グラフに1つの頂点を追加して形成されるリンクレス埋め込みグラフ）の例を示し、YΔY-還元可能グラフがリンクレス埋め込みグラフの適切なサブクラスを形成し、追加の禁制マイナーを持つことを示しました。^[2]実際、ヤミン・ユーが示したように、ピーターセン族の7つを超えて、YΔY-還元可能グラフには少なくとも68,897,913,652の禁制マイナーがあります。^[3]

参考文献

^ ab ロバートソン、ニール;シーモア、PD ;トーマス、ロビン(1993)、「3次元空間におけるグラフのリンクレス埋め込み」、アメリカ数学会誌、28 (1): 84–89、arXiv : math/9301216、doi :10.1090/S0273-0979-1993-00335-5、MR 1164063。
^ abc Truemper, Klaus (1992)、マトロイド分解(PDF)、Academic Press、pp. 100–101。
^ ab Yu, Yaming (2006)、「ワイデルタワイ還元性に対するさらなる禁止マイナー」(PDF)、Electronic Journal of Combinatorics、13 (1): #R7、doi :10.37236/1033。
^ Sachs, Horst (1983)、「平面グラフ上のクラトフスキーの定理の空間類似物について - 未解決問題」、Horowiecki, M.、Kennedy, JW、Sysło, MM (編)、Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981、Lecture Notes in Mathematics、vol. 1018、Springer-Verlag、pp. 230–241、doi :10.1007/BFb0071633、ISBN 978-3-540-12687-4。

[rst93-1] ロバートソン、ニール;シーモア、PD ;トーマス、ロビン(1993)、「3次元空間におけるグラフのリンクレス埋め込み」、アメリカ数学会誌、28 (1): 84–89、arXiv : math/9301216、doi :10.1090/S0273-0979-1993-00335-5、MR 1164063。

[t92-2] Truemper, Klaus (1992)、マトロイド分解(PDF)、Academic Press、pp. 100–101。

[y06-3] Yu, Yaming (2006)、「ワイデルタワイ還元性に対するさらなる禁止マイナー」(PDF)、Electronic Journal of Combinatorics、13 (1): #R7、doi :10.37236/1033。

[4] Sachs, Horst (1983)、「平面グラフ上のクラトフスキーの定理の空間類似物について - 未解決問題」、Horowiecki, M.、Kennedy, JW、Sysło, MM (編)、Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981、Lecture Notes in Mathematics、vol. 1018、Springer-Verlag、pp. 230–241、doi :10.1007/BFb0071633、ISBN 978-3-540-12687-4。