Premium
Oriented walk double covering and bidirectional double tracing
Author(s) -
Hongbing Fan,
Zhu Xuding
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199810)29:2<89::aid-jgt5>3.0.co;2-8
Subject(s) - combinatorics , mathematics , spanning tree , tracing , graph , inverse , discrete mathematics , computer science , geometry , operating system
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 all 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 ). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 89–102, 1998