标题：Oriented walk double covering and bidirectional double tracing
作者：Fan HB.;Zhu XD.
作者机构：[Hongbing, F] Mathematics Department, Shandong University, Jinan Shandong, 250100, China;[ Zhu, X] Department of Applied Mathematics, National Sun Yat 更多
通讯作者地址：[Fan, HB]Shandong Univ, Dept Math, Jinan 250100, Peoples R China.
来源：Journal of Graph Theory
关键词：Oriented walk double covering;Bidirectional double tracing;Retracting free;Odd components
摘要：An oriented walk double covering of a graph G is a set of oriented closed walks, that, traversed successively, combined will have traced each edge of G once in each direction. A bidirectional double tracing of a graph G is an oriented walk double covering that consists of a single closed walk. A retracting in a closed walk is the immediate succession of an edge by its inverse. Every graph with minimum degree 2 has a retracting free oriented walk double covering and every connected graph has a bidirectional double tracing. The minimum number of closed walks in a retracting free oriented walk double covering of G is denoted by c(G). The minimum number of retractings in a bidirectional double tracing of G is denoted by r(G). We shall prove that;for ail connected noncycle graphs G with minimum degree at least 2, r(G) = c(G) - 1. The problem of characterizing those graphs G for which r(G) = 0 was raised by Ore. Thomassen solved this problem by relating it to the existence of certain spanning trees. We generalize this result, and relate the parameters r(G), c(G) to spanning trees of G. This relation yields a polynomial time algorithm to determine the parameters c(G) and r(G). (C) 1998 John Wiley & Sons, Inc. J Graph Theory 29: 89-102, 1998. [References: 8]