What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?
✍ Scribed by Nathaniel Dean
- Publisher
- John Wiley and Sons
- Year
- 1986
- Tongue
- English
- Weight
- 408 KB
- Volume
- 10
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
A digraph D with n vertices is said to be decomposable into a set S of dicycles if every arc of D is contained in exactly one member of S. Counterexamples are given to the following conjectures which are generalizations of three well-known conjectures by G. Hajos, P. Erdos, and P. J. Kelly: (1) [B. Jackson] Every eulerian-oriented graph is decomposable into at most $ dicycles. (2) [W. Bienia & H. Meyniel] Every eulerian digraph is decomposable into at most n dicycles.
Certain observations lead us to make three other conjectures: (a) Every eulerian-oriented graph is decomposable into a t most ? dicycles. (b) Every symmetric digraph with n > 1 is decomposable into at most 2n -3 dicycles. (c) Every eulerian digraph with n > 1 is decomposable into at most $ -3 dicycles.