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

数学のグラフ理論分野において、ナウルグラフは、24頂点36辺を持つ対称二部立方グラフである。ナウルの国旗に描かれた十二芒星にちなんで、デイヴィッド・エプスタインによって命名された。[ 1 ]

彩色数は2、彩色指数は3、直径は4、半径は4、周囲長は6である。 [ 2 ]また、3頂点連結、3辺連結のグラフである。本の厚さは3、列数は2である。 [ 3 ]

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

工事

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

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

ナウルグラフには組み合わせ的な構成法もあります。3つの識別可能なオブジェクトを4つの識別可能なボックスに配置します。各ボックスには1つのオブジェクトしか配置しません。このようにオブジェクトを配置する方法は、グラフの24個の頂点に対応する24通りあります。ある状態から別の状態へ遷移するために、ちょうど1つのオブジェクトを現在の位置から空のボックスに移動できる場合、2つの状態に対応する頂点は辺で結ばれます。結果として得られる状態遷移グラフがナウルグラフです。言い換えれば、配置グラフ です。 あ4、3{\displaystyle A_{4,3}}

代数的性質

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

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

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

ナウルグラフの特性多項式は次のように なる。

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

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

位相的性質

6 つの 12 角面を持つ、種数 4 の表面上のナウル グラフの対称埋め込み。

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

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

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

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

幾何学的特性

単位距離グラフとしてのナウルのグラフ、Žitnik、Horvat、Pisanski (2010)より。

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

歴史

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

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

参考文献

  1. ^ a b c Eppstein, D.、「ナウルグラフの多くの側面」、2007年。
  2. ^ a b Conder, M.および Dobcsányi, P. 「768 頂点までの三価対称グラフ」 J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  3. ^ Wolz, Jessica; SATを用いた線形レイアウトのエンジニアリング。修士論文、テュービンゲン大学、2018年
  4. ^ Sloane, N. J. A. (編). 「数列A110507（交差数nを持つ最小立方グラフのノード数）」 .オンライン整数数列百科事典. OEIS財団.。
  5. ^ Pegg, ET ; Exoo, G. (2009)、「交差数グラフ」、Mathematica Journal、11 (2)、doi : 10.3888/tmj.11.2-2。
  6. ^ Royle, G. F024Aデータ 2011年3月6日アーカイブWayback Machine
  7. ^ Frucht, R. ; Graver, JE; Watkins, ME (1971)、「一般化ピーターセングラフの群」、ケンブリッジ哲学協会紀要、70 (2): 211– 218、Bibcode : 1971PCPS...70..211F、doi : 10.1017/S0305004100049811、S2CID 122686848 。
  8. ^マクマレン、ピーター（1992）、「 2 p頂点を持つタイプ { p , 3}の正多面体」、Geometriae Dedicata、43（3）：285–289、doi：10.1007/BF00151518、S2CID 119591683 。
  9. ^ジトニク、アルジャナ;ホーヴァット、ボリス。Pisanski、Tomaž (2010)、すべての一般化された Petersen グラフは単位距離グラフ(PDF)、IMFM プレプリント、vol. 1109。
  10. ^ Foster, RM (1932)、「電気回路網の幾何学的回路」、アメリカ電気学会誌、51 (2): 309– 317、Bibcode : 1932TAIEE..51..309F、doi : 10.1109/T-AIEE.1932.5056068、S2CID 51638449 。
  11. ^バウワー、IZ; チェルノフ、WW; モンソン、B.; スター、Z (1988)、『フォスター国勢調査』、チャールズ・バベッジ研究センター。
  12. ^ Coxeter, HSM (1950)、「自己双対構成と正則グラフ」、アメリカ数学会報、56 (5): 413– 455、doi : 10.1090/S0002-9904-1950-09407-5。
  13. ^ Zacharias, M. ( 1941)、「Untersuhungen über ebene Konfigurationen (124, 163)」、Deutsche Mathematik、6 : 147–170。
  14. ^ Pegg, Ed (2003), Cubic Symmetric Graphs , Mathematical Association of America, 2013-05-07にオリジナルからアーカイブ、2009-08-20に取得。
「 https://en.wikipedia.org/w/index.php?title=Nauru_graph&oldid=1325564037」より取得