Compatible path-cycle-decompositions of plane graphs (Q1084113): Difference between revisions

Let G be a (multi)graph and \(E_ v\) the edge incident with a vertex v of G. If \(E_{v,0}\subset E_ v\) is a set with an even number of edges incident with v, then a partition \(X_{v,0}\) of \(E_{v,0}\) into 2- element subsets is called a set of transitions at v. If \(E_{v,0}=E_ v\), then \(X_{v,0}\) is called a full set of transitions at v and is denoted by X(v). For a vertex v of G with \(d(v)>2\) a transition t at v is called separating if G-t has more components than G. In the case where two parallel edges e, f join a pair of vertices v and w the transition \(\{\) e,f\(\}\) at v is considered to be distinct from the transition \(\{\) e,f\(\}\) at w. Let \(X=\cup \{X(v)| 2<d(v)\) and d(v)\(\equiv 0(mod 2)\}\). Then X is called a system of transitions of G. If every \(t\in X\) is a nonseparating transition, then X is called nonseparating. For a connected Euler graph G and an Euler trail T (a cycle-decomposition) of G the trail T (cycle-decomposition S) induces in a natural way a system of transitions denoted by \(X_ T\) (respectively, \(X_ S):\) \(t\in X_ T\) \((t\in X_ S)\) if and only if e,f\(\in t\) are consecutive edges in T at a vertex having degree greater than 2. Two systems of transitions X and X' are called compatible if \(X\cap X'=\emptyset\). Suppose X is a set of transitions of a plane graph G. Then X is said to be nonintersecting if for every \(t=\{e,f\}\in X\) the edges e and f are consecutive edges (in the cyclic order induced by the embedding of G in the plane) at the vertex v at which t is defined. For a plane connected graph G and a system of transitions X of G, the transition X is defined to be suitable if (a) X is nonintersecting, and (b) whenever \(t\in X\) is a separating transition of G, then every component of G-t contains an odd vertex of G. A set S of pairwise edge-disjoint paths and cycles covering E(G) is called a path-cycle-decomposition of E(G) if (a) every odd vertex of G is an end-vertex of exactly one path in S, and (b) no even vertex of G is an end-vertex of a path in S. A path-cycle-decomposition S of a graph G induces a transition \(X_ S\) of G where \(t\in X_ S\) if and only if t is a transition at an even vertex having degree at least 4. The authors show that if G is a plane graph and X a system of suitable transitions of G, then there exists a path-cycle-decomposition S of E(G) such that \(T_ S\) is compatible with X.