Partition of an Eulerian circuit search problem for the complete graph of order 15 (Group, Ring, Language and Related Areas in Computer Science)

Abstract

For odd integers 𝓷 greater than or equal to 15, it is known how to construct an Eulerian circuit of the complete graph of order 𝓷 whose shortest subcycle length is 𝓷-4. Furthermore, the author and others have proved that there is no Eulerian circuit of the complete graph of order 𝓷 whose shortest subcycle length is greater than 𝓷-2. The author and others conjecture that, for every odd integer 𝓷 greater than or equal to 15, there is no Eulerian circuit of the complete graph of order 𝓷 whose shortest subcycle length is 𝓷 -3. As part of the proof of the conjecture, the author and others aim to prove that there is no Eulerian circuit of a complete graph of order 15 whose shortest subcycle length is 12. Currently, we expect that the conjecture above for 𝓷 = 15 can be proved through large-scale distributed processing. For distributed processing to be effective, the size of each divided subproblem must be small enough to fit into the main memory. In this report, we describe the methods used to achieve this goal and discuss the possibility of applying these methods to complete the proof.