The Quest for the Eulerian Recurrent Lengths of Complete Bipartite Graphs and Complete Graphs

摘要

The Eulerian recurrent length problem (ERLP) is defined as follows: Inputs to the ERLP consist of a positive integer k and a graph G. The objective of the ERLP is to determine whether there exists an Eulerian circuit, that is, a circuit that contains all of the edges of G, that has no subcycle of length less than k. If G has an Eulerian circuit that has no subcycle of length less than k, and every Eulerian circuit of G has an subcycle of length less than or equal to k, then k is called the Eulerian recurrent length of G, which is abbreviated to the ERL of G, and denoted by ERL(G). In this paper, the ERL's of complete bipartite graphs are given. Furthermore, upper and lower bounds on the ERL's of complete graphs are given. Let m and n be positive even integers with m ≥ n. It is shown that ERL(K_(m,n)) = 2n - 4 if n = m ≥ 4, and ERL(K_(m,n)) = 2n otherwise, where K_(m,n) is the complete bipartite graph whose vertex set V consists of two subsets A containing m vertices and B containing n vertices such that every edge of K_(m,n) connects a vertex in A and one in B. It is also shown that n-4 ≤ ERL(K_n) ≤ n-2 holds for every odd integer n greater than or equal to 7, where K_n is a complete graph consisting of n vertices.