キュービシティ

グラフ理論の数学分野では、立方体性は、ユークリッド空間における軸に平行な単位立方体の交差グラフとしてグラフを実現できる最小の次元として定義されるグラフ不変量である。[1] 立方体性は、1969 年に Fred S. Roberts によって、ユークリッド空間における軸に平行な長方形の交差グラフとしてグラフを表現するため^に必要な最小の次元を考慮する、ボックス性と呼ばれる関連不変量とともに導入された。^{[ 2 ]}

この記事では、有限かつ空でない頂点集合を持つ単純な無向グラフのみを扱います。 ^{[ 3 ] [ 4 ]}

グラフの立方性${\displaystyle G}$、で示される${\displaystyle \operatorname {cub} (G)}$は最小の整数です${\displaystyle k}$そのため${\displaystyle G}$軸平行閉単位の交差グラフとして表現できる${\displaystyle k}$-キューブ${\displaystyle k}$次元ユークリッド空間、${\displaystyle \mathrm {E} ^{k}}$[ ^{5 ] [ 6 ] [ 7 ]​}

のために${\displaystyle k\geq 1}$グラフ${\displaystyle G}$このような表現を持つことができる${\displaystyle \mathrm {E} ^{k}}$かつその場合に限り${\displaystyle G}$は${\displaystyle k}$同じ頂点集合上の無差別グラフ${\displaystyle G}$[ ^{8 ]​}

完全グラフの立方性はゼロと定義される。^{[ 9 ]}

グラフの場合${\displaystyle G,~\operatorname {cub} (G)=0~}$かつその場合に限り${\displaystyle G}$完了しました。^{[ 10 ]}

グラフの場合${\displaystyle G,~\operatorname {cub} (G)=1~}$かつその場合に限り${\displaystyle G}$これは不完全な単位区間グラフである。 ^{[ 11 ]}

のために${\displaystyle n\in \mathbb {N} ^{*}\!,~\operatorname {cub} (K_{1,n})=\lfloor \log _{2}(2n-1)\rfloor ,~}$どこ${\displaystyle K_{1,n}}$は、 (${\displaystyle 1}$中央と）${\displaystyle n}$頂点、および${\displaystyle \lfloor \cdot \rfloor }$は床関数を表します。^{[ 12 ] [ 13 ]}

のために${\displaystyle p\in \mathbb {N} ^{*}\!,~\operatorname {cub} (K_{p(2)})=p,~}$どこ${\displaystyle K_{p(2)}}$は、完全な多部グラフを表します。${\displaystyle p}$枢機卿の部品${\displaystyle 2}$[ ^{14 ] [ 15 ]​}

グラフの場合${\displaystyle G}$の上${\displaystyle n}$頂点、${\displaystyle ~\operatorname {cub} (G)\leq \lfloor 2n/3\rfloor .~}$さらに、この上限は、${\displaystyle n}$[ ^{16 ] [ 17 ]​}