Hypotraceable digraphs |
| |
Authors: | Martin Grtschel Carsten Thomassen Yoshiko Wakabayashi |
| |
Institution: | Martin Grötschel,Carsten Thomassen,Yoshiko Wakabayashi |
| |
Abstract: | A hypotraceable digraph is a digraph D = (V, E) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which D - v is traceable for all ve ∈ V. We prove that a hypotraceable digraph of order n exists iff n ≥ 7 and that for each k ≥ 3 there are infinitely many hypotraceable oriented graphs with a source and a sink and precisely k strong components. We also show that there are strongly connected hypotraceable oriented graphs and that there are hypotraceable digraphs with precisely two strong components one of which is a source or a sink. Finally, we prove that hypo-Hamiltonian and hypotraceable digraphs may contain large complete subdigraphs. |
| |
Keywords: | |
|
|