Bidirectional retracting-free double tracings and upper embeddability of graphs

The author's introduction follows: ``Every connected graph has a double tracing i.e., a closed walk such that every edge is traversed twice. To see this, we replace every edge by a double edge and apply Euler's theorem. A retracting in a double tracing is the immediate succession of an edge by its inverse. In a double tracing a retracting must occur at every vertex of degree 1. By modifying the double tracing, if necessary, we can get a double tracing such that there is no retracting at vertices of degree at least 2. This was shown independently by Eggleton and Skilton and by Sabidussi. As pointed out by the referees, an easy way to see this is to embed the graph in a (possibly nonorientable) surface such that there is exactly one face. The boundary of this face provides the appropriate double tracing. Also, the directed version of Euler's theorem implies that every connected graph has a bidirectional double tracing, i.e., a double tracing in which every edge is traversed once in each direction.In 1951 Ore raised the problem of characterizing the graphs which admit a bidirectional retracting-free double tracing. This variant is surprisingly complicated and seems to have no simple solution from first principles. One may argue that the difficulty lies in the fact that there are graphs for which the above-mentioned surface cannot be chosen to be orientable. In this paper we show how the problem can be solved using the theory of embeddings of graphs and matchings of special 2- polymatroids. We consider in particular cubic graphs since the existence of a bidirectional retracting-free double tracing in a cubic graph is equivalent to the graph being embeddable into a compact orientable two- dimensional manifold such that the manifold minus the graph is a 2-cell; i.e., it is homeomorphic to a disc. We show that a cubic 3-connected graph has this property if the deletion of any three edges leaves either a connected graph or a graph with two components, each of which has a number of vertices congruent to 1 modulo 4. (On the other hand, if we replace each vertex of a cubic 3-connected graph by a triangle, then the resulting graph cannot have this embedding property.) His characterization theorem is as follows: ``A connected multigraph G has a retracting-free bidirectional doubletracing if and only if G has no vertex of degree 1 and has a spanning tree T such that each connected component of G-E(G) either has an even number of edges or contains a vertex which in G has degree at least 4. Moreover, there exists a polynomially bounded algorithm for finding such a tree T or deciding that no such T exists.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Bidirectional retracting-free double tracings and upper embeddability of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751672)