A classification of locally semicomplete digraphs

Abstract

Recently, Huang (1995) gave a characterization of local tournaments. His characterization involves arc-reversals and therefore may not be easily used to solve other structural problems on locally semicomplete digraphs (where one deals with a fixed locally semicomplete digraph). In this paper we derive a classification of locally semicomplete digraphs which is very useful for studying structural properties of locally semicomplete digraphs and which does not depend on Huang's characterization. An advantage of this new classification of locally semicomplete digraphs is that it allows one to prove results for locally semicomplete digraphs without reproving the same statement for tournaments.

We use our result to characterize pancyclic and vertex pancyclic locally semicomplete digraphs and to show the existence of a polynomial algorithm to decide whether a given locally semicomplete digraph has a kernel.