風車のグラフ

グラフ理論の数学分野において、風車グラフWd( k , n )は、k ≥ 2かつn ≥ 2の場合に、完全グラフK _kのn 個のコピーを共通の普遍頂点で結合することによって構築される無向グラフである。つまり、これはこれらの完全グラフの1-クリーク和である。^{[ 1 ]}

頂点数はn ( k − 1) + 1、辺数はnk ( k − 1)/2、^{[ 2 ]}周長は 3 ( k > 2 の場合)、半径は 1、直径は 2 です。中心頂点が関節点であるため、頂点連結度は1 ですが、それを構成する完全グラフと同様に、 ( k − 1)辺連結です。自明に完全であり、ブロック グラフです。

構成上、風車グラフWd(3, n )は友情グラフF _nであり、風車グラフWd(2, n )は星グラフS _nであり、風車グラフWd(3,2)は蝶グラフである。

風車のグラフは彩色数kと彩色指数n ( k − 1 )を持ちます。その彩色多項式は完全グラフの彩色多項式から導き出すことができ、次のようになります。

${\displaystyle x\prod _{i=1}^{k-1}(xi)^{n}.}$

風車グラフWd( k , n )は、 k > 5の場合、優美ではないことが証明されています。^{[ 3 ]} 1979 年に、ベルモンドは、Wd(4, n )はすべてのn ≥ 4に対して優美であると予想しました。^{[ 4 ]}完全差族との同値性により、これはn ≤ 1000に対して証明されています。 ^{[ 5 ]} ベルモンド、コッツィグ、およびタージョンは、k = 4かつn = 2またはn = 3の場合、およびk = 5かつn = 2の場合、 Wd( k , n )は優美ではないことを証明しました。[ ^{6 ]}風車グラフ Wd(3, n )は^、 n ≡ 0 (mod 4)またはn ≡ 1 (mod 4)の場合に限り優美です。^{[ 7 ]}