Abstract
A (di)graph is supereulerian if it contains a spanning eulerian sub(di)graph. This property is a relaxation of hamiltonicity. Inspired by this analogy with hamiltonian cycles and by similar results in supereulerian graph theory, we analyze a number of sufficient Ore type conditions for a digraph to be supereulerian. Furthermore, we study the following conjecture due to Thomassé and the first author: if the arc-connectivity of a digraph is not smaller than its independence number, then the digraph is supereulerian. As a support for this conjecture we prove it for digraphs that are semicomplete multipartite or quasitransitive and verify the analogous statement for undirected graphs.
| Original language | English |
|---|---|
| Pages (from-to) | 8-20 |
| Number of pages | 13 |
| Journal | Journal of Graph Theory |
| Volume | 79 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 May 2015 |
| Externally published | Yes |
Keywords
- arc-connectivity
- degree conditions
- independence number
- quasitransitive digraph
- semicomplete multipartite digraph
- spanning closed trail
- supereulerian digraph