On the recurrent intervals of complete graphs and complete bipartite graphs

摘要

The maximum of the shortest cycle length of Eulerian circuits of an Eulerian graph is called the Eulerian recurrent length of the graph. In this research, it is shown that the Eulerian recurrent length of the complete bipartite graphs K{sub}(n,m) with even n, m and n < m is 2n. For complete graphs of odd order, we have obtained the following results of the searches with computers: the Eulerian recurrent lengths of K{sub}9 and K{sub}11 are 6 and 8, respectively, and, for n = 13, 15, 17, that of K{sub}n is less than n - 2. These results strengthen the conjecture: "If n≥7, then the Eulerian recurrent length of K{sub}n is less than n - 2."