It is NP-complete to find the maximum length of the shortest cycles in Eulerian trails

摘要

It is shown that it is NP-complete to determine the maximum length of the shortest cycles in Eulerian trails of an arbitrary Eulerian graph. By the authors, the maximum length of the shortest cycles in Eulerian trails of an Eulerian graph is referred to as Eulerian recurrent length of the Eulerian graph in previous Technical Reports of IEICE.