数学のグラフ理論の分野における立方体グラフ（りっぽうたいグラフ、）とは、すべての頂点の次数が 3 であるようなグラフのことを言う。言い換えると、立方体グラフとは 3-正則グラフである。立方体グラフは 3価グラフとも呼ばれる。2部立方体グラフ（bicubic graph）とは、立方体グラフかつ2部グラフであるようなグラフのことを言う。
対称性 1932年、は、フォスター調査（Foster census）の皮切りとして、立方体対称グラフの例の集計をはじめた.。設備グラフやピーターセングラフ、ヒーウッドグラフ、、、、、、、、、など、多くの有名なグラフは立方体かつ対称的であった。
は、長さ s の各二つの有向路が、ちょうど一回のグラフの対称性によって互いに写される時、そのような s の最小のものによって対称立方体グラフを分類した。彼は、そのような s は多くとも 5 であることを示し、s が 1 から 5 であるような各グラフの例を提示した.。
半対称立方体グラフには、（最小の半対称立方体グラフ）や、が含まれる。
は、対称性を持たない最小の立方体グラフの二つの内の一つである。それは、単一のとして、恒等自己同型のみを備える。
彩色と独立集合 によると、完全グラフ K4 以外のすべての立方体グラフは、多くとも 3色によって彩色される。したがって、K4 以外のすべての立方体グラフは、少なくとも n/3 個の頂点の独立集合を持つことになる。ここで n はそのグラフ内の頂点の数とする：例えば、3-彩色における最大の色の類は、少なくともこのくらい多くの頂点を含む。
によると、すべての立方体グラフは、その辺彩色のために 3色か 4色を必要とする。3-辺彩色はテイト彩色として知られ、そのグラフの辺を三つの完全マッチングへと区分する。によれば、すべての2部立方体グラフにはテイト彩色が存在する。
テイト彩色が存在しない、橋のない立方体グラフはとして知られる。ピーターセングラフや、、、、、、などが、これに該当する。スナークは無数に存在する.。
位相と幾何 立方体グラフは位相幾何学の分野において、いくつかの方法によって自然に現れる。例えば、1-次元CW複体であるようなグラフを考えた時、立方体グラフは、そのグラフの 0-スケルトンと最大 1-セル接着写像が互いに素であるようなジェネリック（generic）である。立方体グラフはまた、どの頂点においても三つの面が接している正十二面体のような、三次元における単純多面体のグラフとして構成される。
二次元平面上の任意のは、graph-encoded map として知られる立方体グラフの構造によって表現される。この構造において、立方体グラフの各頂点は埋め込みの、すなわち、互いに付帯した頂点、辺および平面の表面からなる組を表す。各旗の三つの隣（neighbor）は、その組の内のどれか一つを変更し、他の二つはそのままにしたものとして得られるような三つの旗である.。
ハミルトン性 立方体グラフのハミルトン性については多くの研究結果がある。1980年にP.G. テイトは、すべての立方多面体グラフはハミルトン閉路を持つと予想した。このテイトの予想に対する反例は、の 46-頂点タットグラフによって、1946年に挙げられた。そのトゥッテは 1971年、すべての 2部立方体グラフはハミルトンであると予想した。しかし、ジョセフ・ホートンは 96-頂点をこの反例として挙げたBondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.。その後、マーク・エリンガムはさらに二つの反例を挙げた：であるEllingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981..。未だに解決のなされていない、テイトとトゥッテの予想の組合せであるでは、すべての二部立方多面体グラフはハミルトンである、としている。立方体グラフがハミルトンであるとき、によってそれを正確に表現することが出来る。
すべての n-頂点立方体グラフの中から一つの立方体グラフが選ばれるとき、それはハミルトンであることが非常に多い： n が無限大へと向かう極限において、n-頂点立方体グラフがハミルトンである割合は 1 となる.。
は、すべての n-頂点立方体グラフは多くとも 2n/3 個（およそ 1.260n 個）の異なるハミルトン閉路を含むと予想し、そのような多くの閉路を含む立方体グラフの例を提供した.。異なるハミルトン閉路の数について証明された最良の上界は、1.276n である.。
他の性質 任意の n-頂点立方体グラフのは、最大でも n/6 である。しかし、立方体グラフのパス幅の知られている下界のうち最良のものは、より小さく、0.082n である.。
グラフ理論を初めて扱った、1736年のレオンハルト・オイラーによる論文の一部分において証明されたによると、すべての立方体グラフの頂点の数は偶数であることが分かる。
ジュリウス・ピーターセンの定理は、の無いすべての立方体グラフには完全マッチングが存在する、というものである.。
ロヴァースとプラマーは、すべての橋の無い立方体グラフには、指数関数的な数の完全マッチングが存在すると予想した。この予想は近年、すべての橋の無い n 頂点立方体グラフには少なくとも 2n/3656 個の完全マッチングが存在する、という結果とともに証明された.。
アルゴリズムと計算量 何人かの研究者は、立方体グラフに限定された指数関数時間アルゴリズムの計算量についての研究を行っている。例えば、グラフのに動的計画法を適用することにより、Fomin と Høie は時間 O(2n/6 + o(n)) 内に彼らの最大独立集合を見つける方法を示した。巡回セールスマン問題は、立方体グラフによって時間 O(1.251n) 内に解くことが出来る.。
いくつかの重要なグラフ最適化問題はAPX困難である。すなわち、それらには近似率がある定数で評価されるような近似アルゴリズムが存在するが、（P=NPでない限り）近似率が 1 へと向かうような多項式時間近似スキームは存在しない。そのような問題には、最小の頂点被覆を見つける問題や最大独立集合、最小支配集合、最大カットを見つける問題などが含まれる.。立方体グラフの（任意のにおいて交叉する辺の最小数）もまた、NP困難であるが、近似出来ることもある.。
出典
関連項目
外部リンク