Loading article…
グラフ理論の数学分野において、グレイグラフは54個の頂点と81個の辺を持つ無向二部グラフである。これは3次グラフであり、すべての頂点はちょうど3つの辺に接している。グレイグラフは1932年にマリオン・C・グレイによって発見され（未発表）、その後1968年にジョン・フォークマンが1967年に提起した質問に答える形でバウワーによって独立に発見された。グレイグラフは、辺推移性を持つが頂点推移性を持たないという代数的性質を持つ3次グラフの最初の既知の例として興味深い（下記参照）。
グレイグラフは、彩色数2、彩色指数3、半径6、直径6を持つ。また、3頂点連結かつ3辺連結の非平面グラフである。
グレイグラフは、3 × 3 × 3 グリッドの 27 個の点と、これらの点を通る 27 本の軸平行線から構築できます( Bouwer 1972 ) 。この点と線の集合は射影構成を形成します。各点にはちょうど 3 本の線が通り、各線にはちょうど 3 個の点があります。グレイグラフはこの構成のレヴィグラフです。構成のすべての点とすべての線に頂点があり、互いに接する点と線のペアごとに辺があります。この構成は (Bouwer 1972) を任意の次元n ≥ 3 に一般化し、グレイグラフと同様の代数的性質を持つn価レヴィグラフを生成します。 (Monson、Pisanski、Schulte、Ivic-Weiss 2007) では、グレイグラフは、ある局所的にトーラス状の抽象的な正 4 次元多面体の辺と三角形の面に対する別の種類のレヴィグラフとして現れます。したがって、これは同様の構造を持つ無限の立方体グラフ族の最初の例である。他のレヴィグラフと同様に、これは二部グラフであり、頂点は二部分割の一方の側の点に対応し、もう一方の側の線に対応する。
MarušičとPisanski (2000) は、グレイグラフを構築するいくつかの代替方法を示しています。任意の二部グラフと同様に、奇数長のサイクルはなく、4 または 6 頂点のサイクルもないため、グレイグラフの周長は8 です。グレイグラフを埋め込むことができる最も単純な有向曲面の種数は 7 です( Marušič、Pisanski & Wilson 2005 )。
グレイグラフはハミルトングラフであり、 LCF表記から構築できる。
ハミルトン三次グラフとして、その彩色指数は3である。
グレイグラフの自己同型群は位数1296の群です。この群はグラフの辺に対して推移的に作用しますが、頂点に対しては推移的に作用しません。つまり、すべての辺を他のすべての辺に写像する対称性は存在しますが、すべての頂点を他のすべての頂点に写像する対称性は存在しません。基となる構成の点に対応する頂点は、点に対応する他の頂点とのみ対称であり、線に対応する頂点は、線に対応する他の頂点とのみ対称です。したがって、グレイグラフは半対称グラフであり、最小の3次半対称グラフです。
グレイグラフの特性多項式は
グレイグラフは、隣接する頂点が単位距離で離れているような平面上の点で表現できます。つまり、単位距離グラフです。 [ 1 ]
![{\displaystyle [-25,7,-7,13,-13,25]^{9}.\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/014e670206b76bab2513b807e955533d50c3efb0)
