オイラーグラフに対して，そのオイラー回路の最短部分閉路長の最大値をそのグラフのオイラー回帰長と呼ぶ．n は正の奇数とし，n個の点からなる完全グラフK_n のオイラー回帰長をe（n）で表す．本報告では，未解決になっている「任意の奇数n≧7に対してe（n）＜n-2 が成り立つ」という予想を解決に導くことを目的とする新しい予想を提案し，さらに，予想の検証のための計算機実験のアルゴリズムの改良について述べる．改良されたアルゴリズムによりe（21）＜19が成り立つことが検証されている．%The maximum of the shortest subcycle length of Eulerian circuits of an Eulerian graph is called the Eulerian recurrent length of the graph. Let n be a positive odd integer, and let e(n) denote the Eulerian recurrent length of the complete graph K_n that consists of n vertices. In this report, a new conjecture expected to lead to the solution of the following unsolved conjecture is proposed: for any odd integer n ≧ 7, e(n) < n — 2 holds. Furthermore, improvement of the algorithm for computer experiments to verify the conjectures is shown. By computer experiments with the improved algorithm, it has been verified that e(21) < 19 holds.
展开▼
