Loading article…
グラフ理論の数学分野において、コクセターグラフは28個の頂点と42個の辺を持つ3正則グラフである。[ 1 ]これは、既知の13個の3次距離正則グラフの1つである。[ 2 ]これはハロルド・スコット・マクドナルド・コクセターにちなんで名付けられた。
コクセターグラフは、彩色数3、彩色指数3、半径4、直径4、周長7です。また、3頂点連結グラフであり、3辺連結グラフでもあります。本の厚さは3、待ち行列数は2です。 [ 3 ]
コクセターグラフは準ハミルトングラフです。つまり、それ自体はハミルトン閉路を持ちませんが、そこから1つの頂点を取り除いて形成されるすべてのグラフはハミルトングラフになります。直線交差数は11で、この交差数を持つ最小の3次グラフです[ 4 ]（OEISのシーケンスA110507）。このグラフは1-平面です。[ 5 ]
コクセターグラフの最も単純な構成は、ファノ平面から行います。7つのオブジェクト上の7C3 = 35通りの可能な3つの組み合わせを取ります。ファノ平面の線に対応する7つのトリプレットを破棄し、28個のトリプレットを残します。互いに素な2つのトリプレットをリンクします。結果として得られるのがコクセターグラフです。（画像を参照。）この構成は、コクセターグラフが奇数グラフO4 （クネーザーグラフKG7,3としても知られる）の誘導部分グラフであることを示しています。
コクセターグラフは、より小さな距離正則なヒーウッドグラフから、ヒーウッドグラフの各6サイクルに対して頂点を、6サイクルの互いに素なペアごとに辺を構築することによって構築することもできます。[ 6 ]
コクセターグラフは、ホフマン・シングルトングラフから導出できます。ホフマン・シングルトングラフの任意の頂点vを取ります。vを含むサイズ15の独立集合が存在します。vの7つの隣接点と、 vを含む独立集合全体を削除すると、コクセターグラフが残ります。
コクセターグラフの自己同型群は位数336の群である。[ 7 ]この群はグラフの頂点、辺、弧に推移的に作用する。したがって、コクセターグラフは対称グラフである。任意の頂点を他の任意の頂点に、任意の辺を他の任意の辺に写像する自己同型が存在する。フォスターの調査によると、F28A と表記されるコクセターグラフは、28 個の頂点を持つ唯一の 3 次対称グラフである。[ 8 ]
コクセターグラフは、隣接行列のグラフ固有値の集合であるグラフスペクトルによって一意に決定されます。[ 9 ]
ハミルトン閉路を含まない有限連結頂点推移グラフであるコクセターグラフは、ロヴァース予想の変形に対する反例となるが、この予想の標準的な定式化ではハミルトン路が要求され、コクセターグラフによって検証される。
ハミルトン閉路を持たない頂点推移グラフの例は 、完全グラフK 2、ピーターセングラフ、コクセターグラフ、およびピーターセングラフとコクセターグラフの各頂点を三角形に置き換えることによって派生した 2 つのグラフの 5 つしか知られていない。[ 10 ]
コクセターグラフの特性多項式はこれは、この特性多項式を持つ唯一のグラフであり、スペクトルによって決定されるグラフである。
これらは、同じ頂点ラベルを使用したコクセターグラフの異なる表現です。色は4色あり、各色に7つの頂点があります。 赤、緑、青の各頂点は、同じ色の2つの頂点（7サイクルを形成する細い辺）と1つの白い頂点（太い辺）に接続されています。
