多面体グラフ

数学の一分野である幾何学的グラフ理論において、多面体グラフは、凸多面体の頂点と辺から形成される無向グラフです。あるいは、純粋にグラフ理論的な用語で言えば、多面体グラフは3 つの頂点で接続された平面グラフです。

凸多面体のシュレーゲル図は、その頂点と辺をユークリッド平面上の点と線分として表し、外側の凸多角形を小さな凸多角形に分割したもの（多面体のグラフの凸描画）を形成する。交差がないため、すべての多面体グラフは平面グラフでもある。さらに、バリンスキーの定理により、 3頂点連結グラフである。

シュタイニッツの定理によれば、これら 2 つのグラフ理論的特性は、多面体グラフを完全に特徴付けるのに十分である。つまり、多面体グラフはまさに 3 頂点連結平面グラフである。つまり、グラフが平面かつ 3 頂点連結である場合、頂点と辺が同型グラフを形成する多面体が存在する。^{[1] [2]}このようなグラフが与えられた場合、凸多角形をより小さな凸多角形に分割したものとしてグラフを表現するには、トゥッテ埋め込みを使用する。^[3]

テイトは、すべての立方多面体グラフ（つまり、各頂点がちょうど 3 つの辺に接する多面体グラフ）にはハミルトン閉路があると予想しましたが、この予想はWT タットの反例である多面体だが非ハミルトンのタットグラフによって反証されました。グラフが立方体であるという要件を緩めると、はるかに小さな非ハミルトン多面体グラフが存在します。頂点と辺の数が最も少ないグラフは、11 頂点 18 辺のハーシェルグラフです^{[4]。また、すべての面が三角形である 11 頂点の非ハミルトン多面体グラフ、}ゴールドナー・ハラリーグラフも存在します^[5]。

さらに強い主張としては、定数（短さ指数）と多面体グラフの無限族が存在し、その族内の -頂点グラフの最長単純経路の長さは となる。^{[6] [7]}${\displaystyle \alpha <1}$${\displaystyle n}$${\displaystyle O(n^{\alpha })}$

デュイヴェスティンは26辺までの多面体グラフの数を示している。^[8] 6、7、8、…辺を持つグラフの数は

1、0、1、2、2、4、12、22、58、158、448、1342、4199、13384、43708、144810、...（OEISのシーケンスA002840）。

多面体グラフを頂点の数で数えることもできる。4、5、6、…頂点を持つグラフの場合、多面体グラフの数は

1、2、7、34、257、2606、32300、440564、6384634、96262938、1496225352、...（OEISの配列A000944）。

プラトン立体のグラフはプラトングラフと呼ばれています。多面体グラフの他のすべての特性を持つだけでなく、これらは対称グラフであり、すべてハミルトン閉路を持ちます。^[9]このようなグラフは5つあります。

• 四面体グラフ– 4 つの頂点、6 つの辺
• 八面体グラフ– 6 頂点、12 辺
• 立方体グラフ– 8 頂点、12 辺
• 20面体グラフ– 12 頂点、30 辺
• 12面体グラフ– 頂点20個、辺30個

多面体グラフは、立方体（すべての頂点に 3 つの辺がある）の場合は単純多面体のグラフであり、最大平面グラフの場合は単体多面体のグラフです。たとえば、四面体、立方体、および十二面体グラフは単純であり、四面体、八面体、および二十面体グラフは単体です。

Halinグラフは、平面埋め込みツリーにツリーのすべての葉を接続する外部サイクルを追加することで形成されるグラフであり、多面体グラフのもう 1 つの重要なサブクラスを形成します。

• ワイスシュタイン、エリック W.、「多面体グラフ」、MathWorld