Locally semicomplete digraphs and generalizations

Jørgen Bang-Jensen*

*Kontaktforfatter for dette arbejde

Publikation: Kapitel i bog/rapport/konference-proceedingKapitel i bogForskningpeer review


The class of locally semicomplete digraphs was discovered by Bang-Jensen in 1988. Locally semicomplete digraphs form a significant generalization of semicomplete digraphs with a very rich structure. The class contains digraphs, such as directed cycles, that are very far from being semicomplete. Yet a large number of classical results for semicomplete digraphs still hold for locally semicomplete digraphs. Two examples are that every connected locally semicomplete digraph is traceable and every strongly connected locally semicomplete digraph has a hamiltonian cycle. Since Bang-Jensen’s paper (J. Graph Theory, 14(3):371–390, 1990, [9]) was published in 1990 there has been a significant amount of research done on the class including several PhD theses. In this chapter we survey a number of important results, both structural and algorithmic, on locally semicomplete digraphs and illustrate various important proof-techniques. Several of the results hold even for some superclasses of locally semicomplete digraphs. Many of the proofs and algorithms rely on a structural characterization of those locally semicomplete digraphs that are not semicomplete (have independence number at least 2). As it turns out, these digraphs fall in two disjoint classes, called round decomposable and evil locally semicomplete digraphs, respectively. The first of these has a structure which allows many problems to be solved efficiently, whereas the second class, the evil locally semicomplete digraphs, has a structure which is much closer to that of semicomplete digraphs and hence requires much more work for many problems.

TitelClasses of Directed Graphs
RedaktørerJørgen Bang-Jensen, Gregory Gutin
ISBN (Trykt)978-3-319-71839-2
ISBN (Elektronisk)978-3-319-71840-8
StatusUdgivet - 2018
NavnSpringer Monographs in Mathematics


Dyk ned i forskningsemnerne om 'Locally semicomplete digraphs and generalizations'. Sammen danner de et unikt fingeraftryk.