scientific article; zbMATH DE number 15867
[For the entire collection see Zbl 0709.00011.] Let \(D=(V(D),A(D))\) be a simple digraph of order \(n\). For each \(v\in V(D)\), denote by \(A(v)=A^ +(v)\cup A^ -(v)\) the set of arcs incident with \(v\), \(A^ -(v)\) being the set of arcs incident to \(v\) and \(A^ +(v)\) the set of arcs incident from \(v\). \(D\) is called an Eulerian digraph if for all \(v\in V(D)\), \(| A^ +(v)|=| A^ - (v)|\). Let \(D(V(D),A(D))\) be a Eulerian digraph; for each \(v\in V(D)\) let be given a partition of \(A(v)\), denoted by \(P(v)\). Call \(P(D)=\bigcup_{v\in V(D)}P(v)\) a system of partitions. In particular, if \(v\in V(D)\) and \(C\in P(v)\) imply \(| C\cap A^ +(v)|=| C\cap A^ -(v)| = 1\), we denote such \(P(D)\) by \(X(D)\). An Eulerian trail \(T=\{v_ 0,a_ 1,v_ 1,a_ 2,\dots,v_{n-1},a_ n,v_ n=v_ 0\}\) is called \(P(D)\)-compatible if no two consecutive arcs \(a_ i\), \(a_{i+1}\) of \(T\) are in the same partition class \(C\in P(v_ i)\) and \(a_ 1\), \(a_ n\) are not in the same partition class of \(P(v_ 0)=P(v_ n)\). In this paper, the concept of `` splitting away arcs in a digraph is introduced and investigated. Using the splitting operation, the authors present some sufficient conditions for a connected Eulerian digraph to have a \(P(D)\)-compatible Eulerian trail and an \(X(D)\)-compatible Eulerian trail, respectively. Moreover, a new double splitting lemma is given.
- Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems
- Almost Eulerian compatible spanning circuits in edge-colored graphs
- Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs
- Eulerian Circuits with No Monochromatic Transitions in Edge-Colored Digraphs with all Vertices of Outdegree Three
- Circular flows of nearly Eulerian graphs and vertex-splitting
- scientific article; zbMATH DE number 4162907 (Why is no real title available?)
- Digraph Decompositions and Eulerian Systems
- Complexity of compatible decompositions of Eulerian graphs and their transformations
- Nowhere‐zero 3‐flows in products of graphs
- Compatible spanning circuits and forbidden induced subgraphs
- Transforming eulerian trails
- Some algorithmic results for finding compatible spanning circuits in edge-colored graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972517)