ラダーグラフ

ラダーグラフ
ラダーグラフL8 。
頂点	⁠ ⁠${\displaystyle 2n}$
エッジ	⁠ ⁠${\displaystyle 3n-2}$
彩色数	⁠ ⁠${\displaystyle 2}$
色指数	${\displaystyle {\begin{cases}3&{\text{if }}n>2\\2&{\text{if }}n=2\\1&{\text{if }}n=1\end{cases}}}$
プロパティ	単位距離 ハミルトン 平面 二部
表記	⁠ ⁠${\displaystyle L_{n}}$
グラフとパラメータの表

数学のグラフ理論の分野において、ラダーグラフ Ln_は2n個の頂点と3n −2個の辺を持つ平面の無向グラフである。^[1]

ラダーグラフは、2つのパスグラフの直積として得られます。そのうちの1つは1つのエッジのみを持ちます：L _{n ,1} = P _n × P ₂。^{[2] [3]}

プロパティ

構築により、ラダーグラフ L _nはグリッドグラフ G _{2, n}と同型であり、 n段の梯子のように見える。これは、内周4（n>1の場合）、彩色指数3（ n>2の場合） のハミルトングラフである。

ラダーグラフの彩色数は 2 であり、その彩色多項式はです。 ${\displaystyle (x-1)x(x^{2}-3x+3)^{(n-1)}}$

ラダーグラフL ₁、L ₂、L ₃、L ₄、L ₅。

• 
  ラダーグラフの彩色数は2です。

ラダー段グラフ

「ラダー グラフ」という用語は、パス グラフ P _2のn 個のコピーのグラフ結合であるn × P ₂ ラダー ラング グラフに使用されることがあります。

ラダーの横木グラフLR ₁、LR ₂、LR ₃、LR ₄、およびLR ₅。

円形ラダーグラフ

円形ラダーグラフ CL _nは、4つの2次頂点を直線で結ぶか、長さn  ≥ 3 の閉路と辺の直積によって構成できます。 ^[4] 記号で表すと、CL _n = C _n × P ₂です。2 n 個のノードと3 n個の辺を持ちます。ラダーグラフと同様に、連結グラフ、平面グラフ、ハミルトングラフですが、 nが偶数の場合にのみ二部グラフとなります。

円形ラダー グラフはプリズムの多面体グラフであるため、一般的にはプリズム グラフと呼ばれます。

円形ラダーグラフ:

CL3

CL4

CL5

CL6

CL7

CL8

メビウスの梯子

標準的なラダー グラフの 4 つの 2 次頂点を十字形に接続すると、メビウス ラダーと呼ばれる 立方グラフが作成されます。

メビウスの梯子M ₁₆の 2 つのビュー。

参考文献

1. Weisstein, Eric W.「ラダーグラフ」。MathWorld。
2. Hosoya, H.およびHarary, F.「3つのフェンスグラフのマッチング特性について」 J. Math. Chem. 12, 211-218, 1993.
3. Noy, M. および Ribó, A.「再帰的に構築可能なグラフ族」Adv. Appl. Math. 32, 350-363, 2004.
4. チェン、イーチャオ;グロス、ジョナサン L.マンスール、トゥフィク（2013 年 9 月）。 「円形はしごの総埋め込み分布」。グラフ理論ジャーナル。74 (1): 32–57。CiteSeerX 10.1.1.297.2183。土井：10.1002/jgt.21690。S2CID  6352288。