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

デューラーグラフG (6,2)。

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

定義と表記

ワトキンスの記法では、グラフは頂点集合 と辺集合 を持つグラフであり、 添え字はと を 法として読み取られる。一部の著者は という記法を使用する。同じグラフに対するコクセターの記法は であり、これはグラフを構成する正n角形と星型多角形のシュレーフリ記号を組み合わせたものである。ピーターセングラフ自体は または である。一部の著者はを認めており、これは正則グラフではないグラフを生成する。^{[ 3 ]}${\displaystyle 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\}}$$ ${\displaystyle n}$ ${\displaystyle k<n/2}$ ${\displaystyle GPG(n,k)}$ ${\displaystyle \{n\}+\{n/k\}}$ ${\displaystyle G(5,2)}$ ${\displaystyle \{5\}+\{5/2\}}$ ${\displaystyle k=n/2}$

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

例

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

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

プロパティ

G (9, 2)の3つのハミルトン閉路のうちの1つ。同じグラフ内の他の2つのハミルトン閉路は、図を40°回転させると対称となる。

このグラフ族は、いくつかの興味深い特性を持っています。例えば：

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

同型性

${\displaystyle G(n,k)}$ は または の場合にのみ と同型である。^{[ 11 ]}${\displaystyle G(n,\ell )}$ ${\displaystyle k\equiv \pm \ell \ (\mathrm {mod} \ n)}$ ${\displaystyle k\ell \equiv \pm 1\ (\mathrm {mod} \ n)}$

胴回り

胴回りは少なくとも3、最大で8であり、特に：^{[ 12 ]}${\displaystyle G(n,k)}$

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

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

状態	胴回り
${\displaystyle n=3k}$	3
${\displaystyle n=4k}$	4
${\displaystyle k=1}$
${\displaystyle n=5k}$	5
${\displaystyle n=5k/2}$
${\displaystyle k=2}$
${\displaystyle n=6k}$	6
${\displaystyle k=3}$
${\displaystyle n=2k+2}$
${\displaystyle n=7k}$	7
${\displaystyle n=7k/2}$
${\displaystyle n=7k/3}$
${\displaystyle k=4}$
${\displaystyle n=2k+3}$
${\displaystyle n=3k\pm 2}$
さもないと	8

彩度数と彩度指数

一般化ピーターセングラフは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です。ヴィジングの定理によれば、これらが唯一の可能性です。^{[ 13 ]}

一般化ピーターセングラフは、 3辺の色分けが1つだけである数少ないグラフの1つです。^{[ 14 ]}${\displaystyle G(9,2)}$

• 
  ピーターセングラフの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辺着色可能ではない唯一の一般化ピーターセングラフである。^{[ 15 ]}

参考文献

1. Coxeter, HSM (1950)、「自己双対構成と正則グラフ」、アメリカ数学会報、56 (5): 413– 455、doi : 10.1090/S0002-9904-1950-09407-5。
2. ワトキンス、マーク・E.（1969）、「テイト彩色定理とその一般化ピーターセングラフへの応用」、組合せ理論ジャーナル、6（2）：152-164、doi：10.1016/S0021-9800（69）80116-X。
3. Alspach, BR (1983)、「ハミルトニアン一般化ピーターセングラフの分類」、Journal of Combinatorial Theory、シリーズB、34 (3): 293– 312、doi : 10.1016/0095-8956(83)90042-4、MR 0714452 。
4. Gross, Jonathan L.; Tucker, Thomas W. (1987), Topological Graph Theory , New York: Wiley例2.1.2、p.58。
5. Campbell, SR; Ellingham, MN ; Royle, Gordon F. (1993)、「十分に被覆された立方グラフの特徴づけ」、Journal of Combinatorial Mathematics and Combinatorial Computing、13 : 193– 212、MR 1220613 。
6. Frucht, R. ; Graver, JE; Watkins, ME (1971)、「一般化ピーターセングラフの群」、ケンブリッジ哲学協会紀要、70 (2): 211– 218、Bibcode : 1971PCPS...70..211F、doi : 10.1017/S0305004100049811。
7. トーマスン、アンドリュー（1982）、「3つのハミルトン閉路を持つ立方グラフは必ずしも一意に辺を彩色できるわけではない」、グラフ理論ジャーナル、6（2）：219-221、doi：10.1002/jgt.3190060218。
8. Schwenk, Allen J. (1989)、「特定の一般化ピーターセングラフにおけるハミルトンサイクルの列挙」、Journal of Combinatorial Theory、シリーズB、47 (1): 53– 59、doi : 10.1016/0095-8956(89)90064-6、MR 1007713 。
9. Haugland, Jan K. (2025), 「一般化ピーターセングラフにおけるハミルトンサイクルの数について」, J. Combin. Math. Combin. Comput. , 126 : 263– 278, arXiv : 2503.08326 , doi : 10.61091/jcmcc126-18。
10. ジトニク、アルジャナ;ホーヴァット、ボリス。Pisanski、Tomaž (2010)、すべての一般化された Petersen グラフは単位距離グラフ(PDF)、IMFM プレプリント、vol. 1109、オリジナル(PDF)から2018-07-24 にアーカイブ、2017-04-07 に取得。
11. Steimle, Alice; Staton, William (2009)「一般化ピーターセングラフの同型類」、離散数学、309 (1): 231– 237、doi : 10.1016/j.disc.2007.12.074
12. Ferrero, Daniela ; Hanusch, Sarah (2014)、「一般化ピーターセングラフの成分接続」(PDF)、International Journal of Computer Mathematics、91 (9): 1940– 1963、doi : 10.1080/00207160.2013.878023、ISSN 0020-7160 、 2018年10月20日にオリジナル(PDF)からアーカイブ、2018年10月20日取得 
13. Castagna, Frank; Prins, Geert Caleb Ernst (1972)、「すべての一般化ピーターセングラフにはTait coloringがある」、Pacific Journal of Mathematics、40 (1): 53– 58、doi : 10.2140/pjm.1972.40.53、ISSN 0030-8730、MR 0304223、Zbl 0236.05106   
14. Bollobás、Béla (2004)、極値グラフ理論、ドーバー、p. 2331978年Academic Press版の再版。
15. Castagna, Frank; Prins, Geert (1972)、「すべての一般化ピーターセングラフにはTait Coloringがある」、Pacific Journal of Mathematics、40 : 53–58、doi : 10.2140/pjm.1972.40.53。