情報処理学会 第78回全国大会講演要旨

著者らは、15個以上の奇数個の点からなる完全グラフのオイラー回路が必ず点の個数よりも3以上小さい長さの部分閉路をもつことを証明した。その証明には計算機による計算の結果を使っているが、現在、より大規模な計算の結果を使って証明の最後の部分の議論を省略することを試みている。詳しくは、負の辺の位置と反転配置の開始位置という2つのオイラー回路上の位置を定義し、点の個数よりも3以上小さい長さの部分閉路をもたないオイラー回路が存在したときに、そのオイラー回路上の特定の長さの範囲で負の辺の位置の個数が常に反転配置の開始位置の個数よりも大きいことが示せれば議論の省略が可能である。その試みと結果について報告する。