A Study of Constraints on Eulerian Circuits (Logic, Algebraic system, Language and Related Areas in Computer Science)

Abstract

The author calls the maximum of the length of a shortest subcycle of an Eulerian circuit of an Eulerian graph the Eulerian recurrence length and pursues the determination of the Eulerian recurrence length e(Kn) of a complete graph Kn with an odd size of the vertex set. So far, the value of e(Kn) has been found for all n < 15, and it has been proved that the inequality n-4 ≦ e(Kn) ≦ n-3 holds for all n ≧ 15. The author conjectures that e(Kn) = n-4 holds for all n ≧ 15 and attempts to prove this conjecture by mathematical induction with e(K₁₅) = 11 as the basis. However, running a simple search algorithm in the computing environment available to the author, it turns out that the search space is too large to prove e(K₁₅) = 11.In this paper, the author proposes to introduce two types of constraints on the edges of the trails to be searched in order to reduce the search space.