Bang-Jensen, J., Guo, Y., Gutin, Gregory and Volkmann, L. (1997) A classification of locally semicomplete digraphs. Discrete Mathematics, 167/168
Full text access: Open
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.
This is a Submitted version This version's date is: 1997 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/e654c468-7eeb-ccc8-d496-748be1df560f/5/
Deposited by Research Information System (atira) on 27-Jan-2013 in Royal Holloway Research Online.Last modified on 27-Jan-2013