No label defined (Q3972517)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 15867
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 15867 |
Statements
25 June 1992
0 references
Eulerian trails
0 references
digraphs
0 references
splitting lemma
0 references
splitting away arcs
0 references
0.793406069278717
0 references
0.7821418642997742
0 references
0.7801778316497803
0 references
0.7789206504821777
0 references
[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.
0 references