TY - CHAP

T1 - Locally semicomplete digraphs and generalizations

AU - Bang-Jensen, Jørgen

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-71840-8_6

DO - 10.1007/978-3-319-71840-8_6

M3 - Book chapter

AN - SCOPUS:85049800712

SN - 978-3-319-71839-2

T3 - Springer Monographs in Mathematics

SP - 245

EP - 296

BT - Classes of Directed Graphs

A2 - Bang-Jensen, Jørgen

A2 - Gutin, Gregory

PB - Springer

ER -