プリズムグラフ

数学のグラフ理論の分野において、プリズムグラフとは、プリズムの 1 つを骨格として持つグラフのことです。

例

個々のグラフは、関連する立体にちなんで命名される場合があります。

三角柱グラフ – 6 つの頂点、9 つの辺
立方体グラフ– 8 頂点、12 辺
五角柱グラフ – 頂点 10 個、辺 15 個
六角柱グラフ – 12 頂点、18 辺
七角柱グラフ – 14 頂点、21 辺
八角柱グラフ – 16 頂点、24 辺
...

幾何学的には、星型多角形は（自己交差し、凸面ではない）異なる一連の角柱多面体の面も形成しますが、これらの星型角柱のグラフは角柱グラフと同型であり、別のグラフのシーケンスを形成しません。

工事

プリズムグラフは、パラメータGP( n ,1)を持つ一般化ピーターセングラフの例である。また、1辺を持つサイクルグラフの直積として構築することもできる。 ^[1]

多くの頂点推移グラフと同様に、プリズムグラフもケイリーグラフとして構築できます。n 次二面体群は、平面における正n角形の対称性のグループです。n角形に対して回転と反射によって作用します。これは、2 $π$ / nの角度による回転と 1 回の反射の 2 つの要素によって生成でき、この生成セットを持つケイリーグラフがプリズムグラフです。抽象的には、このグループは表現 ( rは回転、fは反射または反転) を持ち、ケイリーグラフはrとf (またはr、r ⁻¹、およびf ) を生成元として持ちます。^[1] $\langle r,f\mid r^{n},f^{2},(rf)^{2}\rangle$

nが奇数であるn角柱グラフは循環グラフとして構築できる。しかし、この構築はnが偶数である場合には機能しない。^[1] $C_{2n}^{2,n}$

プロパティ

n角柱のグラフには2 n 個の頂点と 3 n 個の辺があります。これらは正則な立方体グラフです。角柱には各頂点が他の頂点に向かう対称性があるため、角柱グラフは頂点推移グラフです。多面体グラフと同様に、 3 頂点接続の平面グラフでもあります。すべての角柱グラフにはハミルトン閉路があります。^[2]

すべての2連結立方グラフの中で、プリズムグラフは定数倍以内で最大数の1-因数分解を持ちます。1-因数分解は、グラフの辺集合を3つの完全マッチングに分割すること、または同等にグラフの辺を3色で彩色することです。すべての2連結n頂点立方グラフにはO (2 ^{n /2} ) 個の1-因数分解があり、プリズムグラフにはΩ (2 ^{n /2} ) 個の1-因数分解があります。^[3]

n角柱グラフの全域木の数は式^{[4]で与えられる。}

{\frac {n}{2}}{\bigl (}(2+{\sqrt {3}})^{n}+(2-{\sqrt {3}})^{n}-2){\bigr .}

n = 3, 4, 5, ... の場合、これらの数値は

75、384、1805、8100、35287、150528、...（OEISの配列A006235）。

nが偶数値であるn角柱グラフは部分立方体である。これは数少ない既知の無限立方体族の1つであり、（4つの散発的な例を除いて）唯一の頂点推移的な立方体である。 [ ^5]

五角柱は、木幅3のグラフの禁制のマイナーグラフの1つです。^[6]三角柱と立方体グラフの木幅はちょうど3ですが、それより大きな柱グラフの木幅はすべて4です。

参考文献

^ abc Weisstein、Eric W.「プリズムグラフ」。MathWorld。
^ Read, RC および Wilson, RJ An Atlas of Graphs、オックスフォード、イギリス: Oxford University Press、2004 年再版、第 6 章特殊グラフ、 pp. 261、270。
^ Eppstein, David (2013)、「曲げのない3次元直交グラフ描画の複雑さ」、Journal of Graph Algorithms and Applications、17 (1): 35–55、arXiv : 0709.4087、doi :10.7155/jgaa.00283、MR 3019198、S2CID 2716392エプスタインは、プリズムグラフが 1 因数分解の最大数に近いという観察結果を、グレッグクーパーバーグとの個人的なコミュニケーションによるものだと考えています。
^ Jagers, AA (1988)、「プリズムグラフにおけるスパニングツリーの数に関する注記」、International Journal of Computer Mathematics、24 (2): 151–154、doi :10.1080/00207168808803639。
^ Marc, Tilen (2015)、頂点推移立方部分立方体の分類、arXiv : 1509.04565、Bibcode :2015arXiv150904565M。
^ アーンボルグ、ステファン; プロスクロフスキー、アンジェイ;コルニール、デレク G. (1990)、「部分 3 ツリーの禁止マイナー特性」、離散数学、80 (1): 1–19、doi :10.1016/0012-365X(90)90292-P、MR 1045920。
^ ガイ、リチャード K. ;ハラリー、フランク(1967)、「メビウスの梯子について」、カナダ数学速報、10 (4): 493–496、doi : 10.4153/CMB-1967-046-4、MR 0224499。

[mathworld-1] Weisstein、Eric W.「プリズムグラフ」。MathWorld。

[2] Read, RC および Wilson, RJ An Atlas of Graphs、オックスフォード、イギリス: Oxford University Press、2004 年再版、第 6 章特殊グラフ、 pp. 261、270。

[3] Eppstein, David (2013)、「曲げのない3次元直交グラフ描画の複雑さ」、Journal of Graph Algorithms and Applications、17 (1): 35–55、arXiv : 0709.4087、doi :10.7155/jgaa.00283、MR 3019198、S2CID 2716392エプスタインは、プリズムグラフが 1 因数分解の最大数に近いという観察結果を、グレッグクーパーバーグとの個人的なコミュニケーションによるものだと考えています。

[4] Jagers, AA (1988)、「プリズムグラフにおけるスパニングツリーの数に関する注記」、International Journal of Computer Mathematics、24 (2): 151–154、doi :10.1080/00207168808803639。

[5] Marc, Tilen (2015)、頂点推移立方部分立方体の分類、arXiv : 1509.04565、Bibcode :2015arXiv150904565M。

[6] アーンボルグ、ステファン; プロスクロフスキー、アンジェイ;コルニール、デレク G. (1990)、「部分 3 ツリーの禁止マイナー特性」、離散数学、80 (1): 1–19、doi :10.1016/0012-365X(90)90292-P、MR 1045920。

[7] ガイ、リチャード K. ;ハラリー、フランク(1967)、「メビウスの梯子について」、カナダ数学速報、10 (4): 493–496、doi : 10.4153/CMB-1967-046-4、MR 0224499。

例

工事

プロパティ

関連グラフ

参考文献