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

IR (HANDLE) Open Access
  • Jimbo, Shuji
    Graduate School of Natural Science and Technology, Okayama University

Search this article

Description

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.

Journal

  • RIMS Kokyuroku

    RIMS Kokyuroku 2229 81-87, 2022-09

    京都大学数理解析研究所

Keywords

Details 詳細情報について

  • CRID
    1050576966671343232
  • NII Book ID
    AN00061013
  • HANDLE
    2433/279747
  • ISSN
    18802818
  • Text Lang
    en
  • Article Type
    departmental bulletin paper
  • Data Source
    • IRDB

Report a problem

Back to top