ナウルグラフ

ナウルグラフ
ナウルのグラフはハミルトングラフです。
頂点	24
エッジ	36
半径	4
直径	4
胴回り	6
自己同型	144 (S 4 ×S 3 )
彩度数	2
色指数	3
本の厚さ	3
キュー番号	2
プロパティ	対称 立方 ハミルトン 積分 ケイリーグラフ 二部
グラフとパラメータの表

数学のグラフ理論の分野において、ナウルグラフは、24の頂点と36の辺を持つ対称な二部立方グラフである。ナウルの国旗にある12の尖った星にちなんで、デイビッド・エプスタインによって名付けられた。^[1]

彩度数2、彩度指数3、直径4、半径4、胴回り6である。 ^[2]また、3頂点連結、3辺連結のグラフである。本の厚さは3、キュー数は2である。 ^[3]

ナウルグラフは、平面上に描くと少なくとも8つの交差を必要とする。これは、8つの交差を必要とする最小の立方グラフである3つの非同型グラフの1つである。これら3つのグラフのもう1つは、マギーグラフであり、(3-7)ケージとしても知られている。^{[4] [5]}

ナウルグラフはハミルトングラフであり、 LCF表記法で記述できる ：[5, −9, 7, −7, 9, −5] ^4。 [ ^1]

ナウルグラフは、12 角形の頂点を 12 角形の頂点に接続して形成される一般化ピーターセングラフ G (12, 5) として構築することもできます。このグラフでは、 星の各点が 5 ステップ離れた点に接続されます。

ナウル グラフには組み合わせによる構成もあります。3 つの識別可能なオブジェクトを 4 つの識別可能なボックスに配置します。ボックスごとにオブジェクトが 1 つしか入らないようにします。オブジェクトをこのように配置する方法は 24 通りあり、グラフの 24 個の頂点に対応しています。1 つのオブジェクトを現在の場所から空のボックスに移動することで、ある状態から別の状態に移行できる場合、2 つの状態に対応する頂点はエッジで接続されます。結果として得られる状態遷移グラフがナウル グラフです。

ナウルグラフの自己同型群は位数 144 の群である。^[6]これは対称群S ₄とS ₃の直積に同型であり、グラフの頂点、辺、弧に推移的に作用する。したがって、ナウルグラフは対称グラフである（距離推移的ではない）。任意の頂点を任意の他の頂点に、任意の辺を任意の他の辺に取る自己同型を持つ。フォスター国勢調査によると、ナウルグラフは 24 頂点の唯一の立方対称グラフである。^[2]

一般化ピーターセングラフG ( n,k ) は、n  = 10 かつk  =2 の場合、またはk ²  ≡ ±1 (mod  n ) の場合に限り頂点推移的であり、次の 7 つの場合にのみ辺推移的です: ( n,k ) = (4,1)、(5,2)、(8,3)、(10,2)、(10,3)、(12,5)、(24,5)。^{[7]したがって、ナウルグラフは、わずか 7 つの対称な一般化ピーターセングラフのうちの 1 つです。これらの 7 つのグラフには、}立方体グラフ 、ピーターセングラフ、メビウス–カンターグラフ、十二面体グラフ、デザルググラフがあります。 ${\displaystyle G(4,1)}$ ${\displaystyle G(5,2)}$ ${\displaystyle G(8,3)}$ ${\displaystyle G(10,2)}$ ${\displaystyle G(10,3)}$

ナウルグラフは、4つの要素の順列の対称群であるS4のケイリーグラフであり、最初の要素_を他の3つの要素のいずれかと入れ替える3つの異なる方法によって生成されます:(1 2)、(1 3)、(1 4)。

ナウルグラフの特性多項式は

${\displaystyle (x-3)(x-2)^{6}(x-1)^{3}x^{4}(x+1)^{3}(x+2)^{6}(x+3),\ }$

これを積分グラフ、つまりスペクトル全体が整数で構成されるグラフにします。

ナウルグラフは、一般化された正多面体として2つの異なる埋め込みを持っています。1つは、任意のフラグ（頂点、辺、面の3つ組）を他の任意のフラグに取る対称性が存在するように、辺、頂点、面に分割された位相面です。^[8]

これら 2 つの埋め込みのうちの 1 つはトーラスを形成するため、ナウル グラフはトーラス グラフになります。つまり、ナウル グラフの 24 の頂点と 36 の辺とともに 12 の六角形の面で構成されます。この埋め込みの双対グラフは、12 の頂点と 36 の辺を持つ対称 6 正則グラフです。

ナウルグラフのもう1つの対称埋め込みには、6つの12角形の面があり、種数4の表面を形成します。その双対は、各面が他の4つの面と3つの辺を共有するため、単純なグラフではなく、多重グラフです。この双対は、各辺を3つの平行な辺の束に置き換えることで、 正八面体のグラフから形成できます。

これら 2 つの埋め込みのいずれかの面の集合は、他の埋め込みの ペトリー多角形の集合です。

すべての一般化ピーターセングラフと同様に、ナウルグラフは、隣接する頂点が単位距離だけ離れているような方法で平面上の点で表すことができます。つまり、これは単位距離グラフです。^[9]このグラフとプリズムは、図の対称性がn次巡回群を形成するような方法で表すことができない唯一の一般化ピーターセングラフG ( n , p ) です。代わりに、その単位距離グラフ表現は、対称群として 二面体群Dih ₆を持ちます。

ナウルグラフについて最初に書いたのはRMフォスターで、彼はすべての立方対称グラフを収集しようとした。^[10]立方対称グラフのリスト全体は、現在彼にちなんでフォスターセンサスと名付けられており、このリストの中でナウルグラフはグラフF24Aと番号が付けられているが、特定の名前はない。^[11] 1950年にHSMコクセターは、このグラフを2度目に引用し、この記事を説明するために使用されたハミルトン表現を示し、それをザカリアスによって発見された射影構成のレヴィグラフであると説明した。^{[12] [13]}

2003年、エド・ペッグはオンラインのMAAコラムで、F24Aには名前が必要だが、名前を提案しなかったと書いた。^[14]最後に、2007年にデビッド・エップスタインは、ナウル共和国の国旗に、一般化されたピーターセングラフとしてグラフを構築するときに現れるものと似た12ポイントの星があることから、ナウルグラフという名前を使用した。 ^[1]