Loading article…
グラフ理論の数学分野において、ゴールドナー・ハラリーグラフは、 11個の頂点と27個の辺を持つ単純な無向グラフである。これは、1975年に最小の非ハミルトン最大平面グラフであることを証明したアニタ・M・ゴールドナーとフランク・ハラリーにちなんで名付けられた。 [ 1 ] [ 2 ] [ 3 ]同じグラフは、 1967年にブランコ・グリュンバウムによって非ハミルトン単体多面体の例として既に示されていた。[ 4 ]
ゴールドナー・ハラリーグラフは平面グラフです。平面上に描画すると、どの辺も交差しません。平面上に描画すると、すべての面が三角形になるため、極大平面グラフとなります。[ 5 ]すべての極大平面グラフと同様に、 3頂点連結でもあります。つまり、任意の2つの頂点を取り除くと、連結部分グラフが残ります。
ゴールドナー・ハラリーグラフは非ハミルトングラフであり、11個の頂点をそれぞれ一度ずつ通過するサイクルは存在しません。[ 5 ]非ハミルトン多面体グラフの最小頂点数は11です。したがって、ゴールドナー・ハラリーグラフはこのタイプの最小例です。ただし、 11個の頂点を持つ別の非ハミルトン多面体であるハーシェルグラフは、辺の数が少なくなっています。[ 6 ]
ゴールドナー・ハラリーは3木であり、2つの頂点を持つ完全グラフから構築され、グラフがちょうど3つの隣接点を持つまで頂点を繰り返し追加することでクリークを形成します。[ 7 ]他のどのグラフと同様に3-木であり、木幅は3で、グラフは極大である。つまり、木幅を増やさずにこれ以上エッジを追加できない。極大クリークとクリークセパレータはどちらも同じサイズであるため、グラフは弦状である。[ 8 ]平面3-木として、アポロニウスネットワークの例を形成する。[ 9 ]
非ハミルトン最大平面グラフであるゴールドナー・ハラリーグラフは、ブックの厚さが2より大きい平面グラフの例を提供します。言い換えれば、すべての頂点が直線上にあり、すべての辺が直線の片側にとどまる曲線として描かれている平面弧図は存在しません。このような例の存在に基づいて、ベルンハルトとカイネンは、平面グラフのブックの厚さは任意に大きくできると推測しました。[ 10 ]それにもかかわらず、その後、すべての平面グラフのブックの厚さは最大でも4であることが示されました。[ 11 ]
これは、本の厚さが3、彩色数が4、彩色指数が8、周囲が3、半径が2、直径が2で、3辺連結グラフです。
ゴールドナー・ハラリーグラフの自己同型群は位数12であり、回転と鏡映の両方を含む正六角形の対称群である二面体群D6と同型である。
ゴールドナー・ハラリーグラフの特性多項式 は次のとおりです。。
シュタイニッツの定理によれば、ゴールドナー・ハラリー グラフは多面体グラフです。これは 3 連結平面グラフなので、ゴールドナー・ハラリー グラフを骨格とする凸多面体が存在する。[ 12 ]幾何学的には、ゴールドナー・ハラリー グラフは単体多面体、つまり三角形の面を持つ多面体を表します。この多面体は、三角錐の各面に四面体を貼り付けることによって構築され、三角錐のクリートープとなります。 [ 4 ] [ 13 ]四面体が正四面体、つまり面が正三角形で、すべての辺の長さが等しい場合、結果として非凸デルタ面体が得られます。
