Abstract | ||
---|---|---|
AbstractA digraph is supereulerian if it contains a spanning eulerian subdigraph. 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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1002/jgt.21810 | Periodicals |
Keywords | Field | DocType |
supereulerian digraph,spanning closed trail,degree conditions,arc-connectivity,independence number,semicomplete multipartite digraph,quasitransitive digraph | Graph theory,Discrete mathematics,Graph,Independence number,Combinatorics,Multipartite,Hamiltonian (quantum mechanics),Eulerian path,Conjecture,Mathematics,Digraph | Journal |
Volume | Issue | ISSN |
79 | 1 | 0364-9024 |
Citations | PageRank | References |
1 | 0.37 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jørgen Bang-Jensen | 1 | 9 | 2.01 |
Alessandro Maddaloni | 2 | 10 | 2.09 |