The NP-completeness of EULERIAN RECURRENT LENGTH (Algebra, Languages and Computation)
Shuji Jimbo, Yasuaki Oshie, Kosaburo Hashiguchi · Kyoto University Research Information Repository (Kyoto University) · 2005
It is shown that it is $\mathrm{N}\mathrm{P}$ -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 Euterian graph is referred to as Eulerian recurrent length of the Eulerian graph, and the decision problem above is named EULERIAN RECURRENT LENGTH.