立方グラフ

数学のグラフ理論の分野において、 立方グラフはすべての頂点の次数が3 であるグラフです。言い換えると、立方グラフは 3 次正則グラフです。立方グラフは三価グラフとも呼ばれます。

双三次グラフは、三次二部グラフです。

1932 年、ロナルド・M・フォスターは、立方対称グラフの例の収集を開始し、フォスター調査の始まりを形成しました。^[1]ユーティリティ グラフ、ピーターセン グラフ、ヒーウッド グラフ、メビウス–カンター グラフ、パップスグラフ、デザルググラフ、ナウル グラフ、コクセター グラフ、タット–コクセター グラフ、ディクグラフ、フォスター グラフ、ビッグス–スミス グラフなど、多くのよく知られた個々のグラフは、立方かつ対称です。WTタットは、長さsの 2 つの有向パスのそれぞれが、グラフの 1 つの対称性によって互いにマッピングできる最小の整数sによって対称立方グラフを分類しました。彼は、 s が最大で 5 であることを示し、 1 から 5 までの各可能なsの値を持つグラフの例を示しました^。[2]

半対称立方グラフには、グレイ グラフ(最小の半対称立方グラフ)、リュブリャナ グラフ、およびTutte 12 ケージが含まれます。

フルヒトグラフは対称性を持たない5つの最小の立方グラフのうちの1つである。^[3]フルヒトグラフは、恒等自己同型という1つのグラフ自己同型のみを持つ。 ^[4]

ブルックスの定理によれば、完全グラフ K ₄以外のすべての連結立方グラフには、最大 3 色の頂点彩色があります。したがって、 K ₄以外のすべての連結立方グラフには、少なくともn /3 個の頂点の独立したセットがあります。ここで、 n はグラフ内の頂点の数です。たとえば、3 彩色における最大の色クラスには、少なくともこれだけの頂点があります。

ヴィジングの定理によれば、すべての 3 次グラフは辺彩色に 3 色または 4 色を必要とします。3 辺彩色はテイト彩色と呼ばれ、グラフの辺を 3 つの完全マッチングに分割します。ケーニッヒの線彩色定理によれば、すべての 2 次 3 次グラフにはテイト彩色が存在します。

テイトカラーリングを持たないブリッジレス立方グラフはスナークとして知られている。これらには、ピーターセングラフ、ティーツェグラフ、ブラヌーシャスナーク、フラワースナーク、ダブルスタースナーク、シェケレススナーク、ワトキンススナークなどがある。異なるスナークの数は無限にある。^[5]

立方体グラフは、位相幾何学においていくつかの方法で自然に生じます。たとえば、2g-2頂点を持つ立方体グラフは、種数g ≥ 2の曲面をパンツのペアに切断するさまざまな方法を表します。グラフを1 次元CW 複合体と見なすと、立方体グラフは、ほとんどの 1 セル接続マップがグラフの 0 スケルトンと分離しているという点で汎用的です。立方体グラフは、3 次元の単純多面体、つまり 3 つの面がすべての頂点で交わる特性を持つ正十二面体などの多面体のグラフとしても形成されます。

2次元面上の任意のグラフ埋め込みは、グラフエンコードマップと呼ばれる立方グラフ構造として表現できます。この構造では、立方グラフの各頂点は埋め込みのフラグ、つまり頂点、辺、面の相互接続された3つ組を表します。各フラグの3つの隣接フラグは、この相互接続された3つ組の1つのメンバーを変更し、他の2つのメンバーを変更しないことで得られる3つのフラグです。^[6]

立方グラフのハミルトン性については多くの研究がなされている。1880年、PG テイトは、すべての立方多面体グラフにはハミルトン閉路があると予想した。 ウィリアム・トーマス・タットは、 1946年にテイトの予想に対する反例として、46頂点のタットグラフを示した。1971年、タットは、すべての2次3次グラフはハミルトンであると予想した。しかし、ジョセフ・ホートンは、96頂点のホートングラフという反例を示した。^[7]その後、マーク・エリンガムは、さらに2つの反例、エリンガム・ホートングラフを構築した。^{[8] [9]} テイトとタットの予想を組み合わせた未解決のバーネット予想は、すべての2次3次多面体グラフはハミルトンであると述べている。 3次グラフがハミルトングラフである場合、LCF 表記法を使用すると簡潔に表現できます。

n頂点の立方グラフの中から一様にランダムに選ばれた立方グラフは、ハミルトングラフである可能性が非常に高い。nが無限大に近づくにつれて、ハミルトングラフであるn頂点の立方グラフの割合は1に近づく。^[10]

デイヴィッド・エプスタインは、 n頂点の立方グラフには最大で2n/3（約1.260n）個の異なるハミルトン閉路がある^と予想し^、その数の閉路を持つ立方グラフの例を示しました。^[11]異なるハミルトン閉路の数の最も証明された推定値は です。^[12]${\displaystyle O({1.276}^{n})}$

数学における未解決の問題:

-頂点立方グラフの最大パス幅はどれくらいですか?${\displaystyle n}$

（数学における未解決の問題がさらに増える）

任意のn頂点立方グラフのパス幅は最大でもn /6である。立方グラフのパス幅の最もよく知られている下限は0.082 nである。この下限とn /6の上限の間のギャップを縮小する方法は知られていない。 ^[13]

1736 年にレオンハルト・オイラーがグラフ理論に関する最初の論文の一部として証明した握手補題から、すべての立方体グラフには偶数個の頂点があること がわかります。

ピーターセンの定理によれば、すべての立方ブリッジレスグラフには完全マッチングが存在する。[14] ロヴァースとプラマーは、すべての立方ブリッジレスグラフには指数関数的な数の完全マッチング^が 存在すると予想した。この予想は最近証明され、n頂点を持つすべての立方ブリッジレスグラフには少なくとも2 ^n/3656個の完全マッチングが存在することが示された。^[15]

立方グラフに限定された指数時間アルゴリズムの複雑さを研究した研究者は数多くいる。例えば、グラフのパス分解に動的計画法を適用することで、FominとHøieは最大独立集合を^{2n /6+o( n )}の時間で見つける方法を示した。^{[13]立方グラフの}巡回セールスマン問題は、O( ^1.2312n )の時間と多項式空間で解くことができる。 ^{[16] [17]}

いくつかの重要なグラフ最適化問題はAPX 困難です。つまり、近似率が定数で制限される近似アルゴリズムはありますが、 P=NPでない限り、近似率が 1 に近づく多項式時間近似スキームはありません。これらには、最小頂点カバー、最大独立集合、最小支配集合、最大カットを見つける問題が含まれます。^[18]立方グラフの交差数 (任意のグラフ描画で交差する辺の最小数) も、立方グラフではNP 困難ですが、近似することはできます。^{[19]立方グラフ上の}巡回セールスマン問題 は、1153/1152 未満の係数で近似することがNP 困難であることが証明されています。 ^[20]

ウィキメディア・コモンズには、 3 次正則グラフに関連するメディアがあります。

• 単純な3次グラフの表

• Royle, Gordon. 「Cubic symmetric graphs (The Foster Census)」。2011 年 10 月 23 日にオリジナルからアーカイブされました。
• Weisstein、Eric W.「バイキュービックグラフ」。MathWorld。
• Weisstein、Eric W.「キュービックグラフ」。MathWorld。
• ブリンクマン、グンナール。ゲッジバー、ヤン。ヴァン・クリムプット、ニコ (2013)。 「3次グラフ生成の歴史」（PDF）。内部。 Ｊ．Ｃｈｅｍ．モデリング。5 (2-3)。ノバサイエンス: 67–89。ISSN  1941-3955。