トゥッテ 12 ケージ

トゥッテ 12 ケージ
トゥッテ12ケージ
名前の由来	WT トゥッテ
頂点	126
エッジ	189
半径	6
直径	6
胴回り	12
自己同型	12096
彩度数	2
色指数	3
属	17
プロパティ	立方 ケージ ハミルトニアン 半対称 二部
グラフとパラメータの表

数学のグラフ理論の分野において、タット12ケージまたはベンソングラフ^[1]は、126の頂点と189の辺を持つ3正則グラフである。WTタットにちなんで名付けられた。^[2]

タット12ケージは、唯一の(3-12)ケージ（OEISの配列A052453）である。1966年にCTベンソンによって発見された。^[3]彩色数 は2（二部）、彩色指数は3、胴回りは12（12ケージとして）、直径は6である。交差数は165未満であることが知られている（Wolfram MathWorldを参照）。^{[4] [5]}

タット12ケージは3次 ハミルトングラフであり、 LCF表記法[17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17] ^{7 で}定義される。^[6]

コーエンとティッツによって証明されたように、同型性を除いて、(2,2)の 一般化された六角形は正確に 2 つ存在します。それらは分割されたケイリー六角形H(2)とその点線双対です。明らかに、どちらも同じ接続グラフを持ち、それは実際にタット 12 ケージと同型です。^[1]

バラバン11ケージは、トゥッテ12ケージから小さなサブツリーを削除し、結果として生じる2次頂点を抑制することで構築できます。^[7]

Tutte 12-cage の自己同型群は位数が 12,096 で、射影特殊ユニタリ群PSU(3,3) と巡回群Z /2 Zの半直積である。^[1]これは辺には推移的に作用するが頂点には作用しないため、半対称グラフ、つまり辺は推移的だが頂点は推移的ではない正則グラフとなる。実際、Tutte 12-cage の自己同型群は二部部分を保持し、各部分に原始的に作用する。このようなグラフは双プリミティブグラフと呼ばれ、立方双プリミティブグラフは 5 つしか存在しない。これらは Iofinova-Ivanov グラフと名付けられ、位数は 110、126、182、506、990 である。^[8]

768頂点までの立方半対称グラフはすべて知られています。Conder 、Malnič、Marušič、Potočnikによると、Tutte 12ケージは126頂点の唯一の立方半対称グラフであり、グレイグラフ、110頂点のイオフィノバ-イワノフグラフ、リュブリャナグラフ、内周8の120頂点のグラフに次いで5番目に小さい立方半対称グラフです。[ 9 ^]

タット12ケージの 特性多項式は

${\displaystyle (x-3)x^{28}(x+3)(x^{2}-6)^{21}(x^{2}-2)^{27}.\ }$

これはこの特性多項式を持つ唯一のグラフであるため、12 ケージはそのスペクトルによって決定されます。

• 
  Tutte 12 ケージの彩度数は2 です。
• 
  Tutte 12 ケージの色指数は 3です。