一般化ピーターセングラフ

グラフ理論において、一般化ピーターセングラフは、正多角形の頂点を星型多角形の対応する頂点に接続することによって形成される立方グラフの族である。これにはピーターセングラフが含まれ、ピーターセングラフの構築方法の1つを一般化している。一般化ピーターセングラフ族は、1950年にHSMコクセター^[1]によって導入され、1969年にマークワトキンス^[2]によってその名前が付けられた。

ワトキンスの記法では、G ( n , k ) は頂点集合が

${\displaystyle \{u_{0},u_{1},\ldots ,u_{n-1},v_{0},v_{1},\ldots ,v_{n-1}\}}$

エッジセット

${\displaystyle \{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}\mid 0\leq i\leq n-1\}}$

ここで、添え字はn を法として読み取られ、k < n /2です。著者によってはGPG ( n , k ) という表記法を使用しています。同じグラフに対する Coxeter の表記法は { n } + { n / k } で、グラフを形成する正n角形と星型多角形のSchläfli 記号の組み合わせです。Petersen グラフ自体はG (5, 2) または {5} + {5/2} です。

一般化されたピーターセングラフは、2つの頂点、2つの自己ループ、および1つの他の辺を持つ電圧グラフから構築することもできます。 ^[3]

一般化されたピーターセングラフには、nプリズムG ( n ,1)、デューラーグラフ G ( 6,2)、メビウス・カントールグラフ G (8,3)、十二面体 G (10,2)、デザルググラフ G (10,3)、ナウルグラフ G (12,5)がある。

一般化されたピーターセングラフの4つ、すなわち3次元プリズム、5次元プリズム、デューラーグラフ、G (7, 2)は、立方体、3頂点連結、十分に被覆された（つまり、すべての最大独立集合のサイズが等しい）7つのグラフの中に含まれています。 ^[4]

このグラフ族には、いくつかの興味深い特性があります。たとえば、次のようになります。

• G ( n , k )が頂点推移的（つまり任意の頂点を他の任意の頂点に移す対称性を持つ）であるのは、( n , k )=(10,2)またはk2≡  ±1(modn  )^の場合のみである。
• G ( n , k )は、次の7つの場合にのみ辺推移的（任意の辺を他の任意の辺に接続する対称性を持つ）である：( n , k )=(4,1),(5,2),(8,3),(10,2),(10,3),(12,5),(24,5)。^[5]したがって、これら7つのグラフは、対称的な一般化ピーターセングラフである。
• G ( n , k ) が二部であるのは、 nが偶数でkが奇数のときのみです。
• G ( n , k ) がケイリーグラフとなるのは、 k ²  ≡ 1 (mod  n )の場合のみです。
• G ( n , k ) は、 n が6 を法として 5 と合同で、k = 2、n − 2、または ( n ± 1)/2 のとき、低ハミルトンである ( kのこの 4 つの選択により同型グラフが得られる)。また、n が4 で割り切れるか、少なくとも 8 に等しく、k = n /2 のときも非ハミルトンである。その他の場合はハミルトン閉路を持つ。^[6] nが 6 を法として 3 と合同なとき、G ( n , 2) にはちょうど 3 つのハミルトン閉路がある。^[7] G ( n , 2)の場合、ハミルトン閉路の数はnの 6 を法として合同な類に依存し、フィボナッチ数を含む式で計算できる。^[8]
• すべての一般化ピーターセングラフは単位距離グラフである。^[9]

G ( n , k )がG ( n , l )と同型となるのは、 k=lまたはkl≡  ±1(mod  n )のときのみである。^[10]

G ( n , k )の胴回りは少なくとも3、最大8であり、具体的には^[11]

${\displaystyle g(G(n,k))\leq \min \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\right\}.}$

正確な胴回りの値を示す表:

一般化されたピーターセングラフは次数3の正則グラフであるため、ブルックスの定理によれば、その彩色数は 2 または 3 に限られます。より正確には、

${\displaystyle \chi (G(n,k))={\begin{cases}2&2\mid n\land 2\nmid k\\3&2\nmid n\lor 2\mid k\\\end{cases}}}$

ここで、 は論理積 を表し、 は論理和 を表します。ここで、は割り切れることを表し、 は否定を表します。たとえば、 の彩色数は3 です。 ${\displaystyle \land}$${\displaystyle \lor}$${\displaystyle \mid}$${\displaystyle \nmid}$${\displaystyle G(5,2)}$

• 
  ピーターセングラフの3色化または${\displaystyle G(5,2)}$
• 
  デザルググラフの2色化または${\displaystyle G(10,3)}$
• 
  デューラーグラフの3色塗りまたは${\displaystyle G(6,2)}$

ピーターセングラフはスナークグラフなので彩度指数は4で、辺には4色が必要です。他の一般化されたピーターセングラフの彩度指数は3です。ヴィジングの定理によれば、これらが唯一の可能性です。^[12]

一般化ピーターセングラフG (9, 2)は、3辺彩色が1つだけある数少ないグラフの1つである。^[13]

• 
  ピーターセングラフの4辺彩色または${\displaystyle G(5,2)}$
• 
  デューラーグラフの3辺彩色または${\displaystyle G(6,2)}$
• 
  正十二面体の3辺の色分けまたは${\displaystyle G(10,2)}$
• 
  デザルググラフの3辺彩色または${\displaystyle G(10,3)}$
• 
  ナウルグラフの3辺色付けまたは${\displaystyle G(12,5)}$

ピーターセングラフ自体は、3辺が着色できない唯一の一般化ピーターセングラフである。^[14]

グラフG ( n , 2 )とG ( n , 3 )のすべての完全2色化の許容行列がすべて列挙される。^[15]