scientific article; zbMATH DE number 15867

From MaRDI portal
Publication:3972517





[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.











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)