On the Eulerian recurrent lengths of complete bipartite graphs and complete graphs

An Eulerian circuit of a graph is a circuit that contains all of the edges of the graph. A graph that has an Eulerian circuit is called an Eulerian graph. The Eulerian recurrent length of an Eulerian graph G is the maximum of the length of a shortest subcycle of an Eulerian circuit of G. In other words, if every Eulerian circuit of an Eulerian graph G has a subcycle of length less than or equal to l, and there is an Eulerian circuit of G that has no subcycle of length less than l, then the Eulerian recurrent length of G is l . The Eulerian recurrent length of graph G is abbreviated to the ERL of G , and denoted by ERL( G ). In this paper, the ERL's of complete bipartite graphs are given. Let m and n be positive even integers with m ≥ n . It is shown that ERL( K m,n ) = 2 n − 4 if n = m ≥ 4, and ERL( K m,n ) = 2 n otherwise. Furthermore, upper and lower bounds on the ERL's of complete graphs are given. It is shown that n − 4 ≤ ERL( K n ) ≤ n − 2 holds for every odd integer n greater than or equal to 7.