抄録
A-024
キャタピラ上のグラフ・シェアリング・ゲーム
○高橋俊彦（新潟大）・佐藤拓哉（佐渡汽船）
グラフ・シェアリング・ゲームとは，二人のプレイヤーが非負の重み付き連結グラフの頂点を交互に一つずつ取り合い，獲得した頂点の重さの総和の多い方を勝者ゲームである．ただし，二人のプレイヤーは取り除かれた頂点が常に元のグラフで連結グラフを誘導するように頂点を選択しなければならない.
本稿ではキャタピラ，すなわちグラフの全頂点が中心となるパスから距離1以内にあるような木，である場合に，先手が獲得できる重み和を評価した．
