An upper bound for the Hamiltonicity exponent of finite digraphs

✍ Scribed by Günter Schaar; A. Pawel Wojda

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 136 KB
• Volume: 164
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00066-0

✦ Synopsis

Let D be a strongly k-connected digraph of order n/> 2. We prove that for every l >i n/2k the power D t of D is Hamiltonian. Moreover, for any k >/1 and n > 2k we exhibit a strongly k-connected digraph D of order n such that D rn/2kl-1 is non-Hamiltonian.

We use standard terminology, unless otherwise stated. A digraph D = (V, A) of order n/> 2 is said to be strongly q-arc Hamiltonian if for any system S of mutually vertex-disjoint paths of the complete symmetric digraph with vertex set V of total length not greater than q, the digraph D'= (V;AuS) has a Hamiltonian cycle containing S.

If D is such a digraph that for every set W of vertices such that I W I ~< p the digraph D -W is strongly q-arc Hamiltonian, then we say that D is strongly (p, q)-Hamiltonian. It is clear that a strongly (0, 1)-Hamiltonian digraph is strongly Hamiltonian connected, that is, for every pair of vertices u, v ~ V there is a Hamiltonian path from u to v. In [13 Bermond proved the following.