On the Eulerian recurrent lengths of complete bipartite graphs and complete graphs
On the Eulerian recurrent lengths of complete bipartite graphs and complete graphs
复制标题
关于完全二分图和完全图的欧拉循环长度
DOI：
10.1088/1757-899x/58/1/012019
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Jimbo
中科院分区：
文献类型：
--
作者：
S. Jimbo
图的欧拉电路是包含图形的所有边缘的电路。尤拉利亚电路G的亚周期。换句话说，如果欧拉图G的每个欧拉电路的长度小于或等于l，并且有一个欧拉G的电路没有小于L的长度，然后G的Eulerian复发长度为l。给出了完整的两分图的ERL。 = 2n否则，给出了完整图的ERL上的上限和下限。
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(Km,n) = 2n − 4 if n = m ≥ 4, and ERL(Km,n) = 2n otherwise. Furthermore, upper and lower bounds on the ERL's of complete graphs are given. It is shown that n − 4 ≤ ERL(Kn) ≤ n − 2 holds for every odd integer n greater than or equal to 7.