会议论文详细信息
2014 International Conference on Manufacturing, Optimization, Industrial and Material Engineering
On the Eulerian recurrent lengths of complete bipartite graphs and complete graphs
Jimbo, Shuji^1
Graduate School of Natural Science and Technology, Okayama University, 3-1-1 Tsushima-naka, Kita-ku, Okayama-shi, Okayama 700-8530, Japan^1
关键词: Complete bipartite graphs;    Complete graphs;    Eulerian;    Eulerian circuits;    Eulerian graphs;    Odd integers;    Sub-cycle;    Upper and lower bounds;   
Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/58/1/012019/pdf
DOI  :  10.1088/1757-899X/58/1/012019
来源: IOP
PDF
【 摘 要 】

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.

【 预 览 】
附件列表
Files Size Format View
On the Eulerian recurrent lengths of complete bipartite graphs and complete graphs 633KB PDF download
  文献评价指标  
  下载次数:14次 浏览次数:32次