^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Mathematical Sciences. Brunel University, West London^{3} unknown

Abstract:

This note is motivated by A.Kemnitz and B.Greger, Congr. Numer. 130 (1998)127-131. We show that the main result of the paper by Kemnitz and Greger is an easy consequence of the characterization of hamiltonian out-locally semicomplete digraphs by Bang-Jensen, Huang, and Prisner, J. Combin. Theory Ser. B 59 (1993) 267-287. We also disprove a conjecture from the paper of Kemnitz and Greger. There are numerous and various su#cient conditions for hamiltonicity of undirected graphs. For directed graphs not so many are known. One of the main reasons for this situation is the fact that the cycle structure of digraphs is significantly more complicated. As a result, several attempts to generalize su#cient conditions for hamiltonicity of undirected graphs to directed ones have failed. One such example is provided in [3], where the authors describe a family of counterexamples to a `natural ' extension of Fan's su#cient condition [5] for an undirected graph to be hamiltonian. In this note we give another, more striking, example of this kind, which disproves a conjecture from [6]. We also show that the main result of [6] 1 is an easy consequence of the characterization of hamiltonian out-tournaments by Bang-Jensen, Huang and Prisner [4]. For further information and references on hamiltonian digraphs, see e.g. the chapter on hamiltonicity in [1] as well as recent survey papers [2, 8]. We use the standard terminology and notation on digraphs as described in [1]. A digraph D has vertex set V (D) and arc set A(D). If xy A(D), we say that x dominates y and that x and y are adjacent. The subdigraph of D induced by a set X V (D) is denoted by D#X#. A digraph D is strong if either D has only one vertex or there is a path from x to y and a path from y to x for every pair x, y of distinct vertices in D.

Type:

Journal article

Language:

English

Published in:

Australasian Journal of Combinatorics, 2001, Vol 23, p. 115-118