A-005
多次元立方体グラフの部分グラフの内点サイズの最大値を導く再帰方程式の解法

○神保秀司（岡山大）

正整数 k に対して，k 次元立方体グラフ Q_k を k 次元ユークリッド空間上の 2^k 個の点からなる集合 V = {0, 1}^k を点集合とし，2点 v と w の異なる座標が丁度1つであることが v と w を結ぶ辺が存在するための必要十分条件であるものとして定義する．何らかの正整数 k に対する k 次元立方体グラフを総称して多次元立方体グラフと呼ぶことにする．k 次元立方体グラフの n 個の点による誘導部分グラフの内点のサイズ i(k,n) の最大値を表す再帰方程式とその解が知られているが，従来の解法では，再帰方程式の解が i(k,n) と一致することを使っていた．本報告では，上記の再帰方程式を i(k,n) を直接使わないで解く解法を提案する．