レヴィグラフ

レヴィグラフ
パップスグラフは、パップス構成から形成された 18 個の頂点を持つレヴィ グラフです。1 文字でラベル付けされた頂点は構成内の点に対応し、3 文字でラベル付けされた頂点は 3 点を通る線に対応します。
胴回り	≥ 6
グラフとパラメータの表

組合せ数学において、レヴィグラフまたは接続グラフは、接続構造に関連付けられた二部グラフです。^{[1] [2]}接続幾何学または射影構成内の点と線のコレクションから、点ごとに1つの頂点、線ごとに1つの頂点、および点と線の間のすべての接続ごとに1つの辺を持つグラフを形成します。これらは、1942年にそれらについて書いたフリードリヒヴィルヘルムレヴィにちなんで名付けられました。 ^{[1] [3]}

点と線のシステムのレヴィグラフは、通常、内周が少なくとも 6 です。つまり、4閉路はすべて、同じ 2 点を通る 2 本の線に対応します。逆に、内周が少なくとも 6 の任意の二部グラフは、抽象的な接続構造のレヴィグラフとして見ることができます。^[1]構成のレヴィグラフは双正則であり、内周が少なくとも 6 の任意の双正則グラフは、抽象的な構成のレヴィグラフとして見ることができます。^[4]

レヴィ グラフは、ユークリッド空間内の点と平面の間の接続など、他の種類の接続構造に対しても定義できます。すべてのレヴィ グラフには、同等のハイパーグラフが存在し、その逆も同様です。

• デザルググラフは、10 個の点と 10 本の直線で構成されるデザルグ配置のレヴィグラフです。各直線には 3 個の点があり、各点を通過する直線は 3 本あります。デザルググラフは、一般化されたピーターセングラフG(10,3) またはパラメータが 5,2 の二部クネザーグラフとして見ることもできます。これは 20 個の頂点を持つ 3 正則グラフです。
• ヒーウッドグラフは、ファノ平面のレヴィグラフです。これは (3,6)-ケージとも呼ばれ、14 個の頂点を持つ 3-正則グラフです。
• メビウス・カントールグラフは、ユークリッド平面上の直線では実現できない 8 点と 8 本の直線のシステムであるメビウス・カントール構成のレヴィグラフです。これは 16 の頂点を持つ 3 正則グラフです。
• パプスグラフは、9 つ​​の点と 9 つの直線で構成されるパプス配置のレヴィ グラフです。デザルグ配置と同様に、各直線には 3 つの点があり、各点を通過する直線は 3 本あります。これは 18 個の頂点を持つ 3 正則グラフです。
• グレイ グラフは、27 個の点とそれらを通る 27 本の直交線のグリッドとして実現できる構成のレヴィ グラフです。${\displaystyle \mathbb {R} ^{3}}$${\displaystyle 3\times 3\times 3}$
• タットの8ケージは、クレモナ・リッチモンド配置のレヴィグラフです。これは (3,8) ケージとも呼ばれ、30 個の頂点を持つ 3 正則グラフです。
• 4 次元の超立方体グラフは、 相互に接する 2 つの四面体の点と平面によって形成されるメビウス配置のレヴィ グラフです。${\displaystyle Q_{4}}$
• 112頂点のリュブリャナグラフはリュブリャナ構成のレヴィグラフである。^[5]

• Weisstein、Eric W.「Levi Graph」。MathWorld。