Classes of directed graphs

Description

Intro Preface Highlights Technical Remarks Acknowledgements Contents 1. Basic Terminology, Notation and Results 1.1 Sets, Matrices, Vectors and Hypergraphs 1.2 Digraphs, Subgraphs, Neighbours, Degrees 1.3 Walks, Trails, Paths, Cycles and Path-Cycle Subgraphs 1.4 Isomorphism and Basic Operations on Digraphs 1.5 Strong Connectivity 1.6 Linkages 1.7 Undirected Graphs and Orientations of Undirected and Directed Graphs 1.8 Trees in Digraphs 1.9 Flows in Networks 1.10 Polynomial and Exponential Time Algorithms, SAT and ETH 1.11 Parameterized Algorithms and Complexity 1.12 Approximation Algorithms2. Tournaments and Semicomplete Digraphs 2.1 Special Tournaments 2.2 Basic Properties of Tournaments and Semicomplete Digraphs 2.2.1 Median Orders, a Powerful Tool 2.2.2 Kings 2.2.3 Scores and Landau's Theorem 2.3 Spanning k-Strong Subtournaments of Semicomplete Digraphs 2.4 The Second Neighbourhood Conjecture 2.4.1 Fisher's Original Proof 2.4.2 Proof Using Median Orders 2.4.3 Relation with Other Conjectures 2.5 Disjoint Paths and Cycles 2.5.1 Polynomial Algorithms for Linkage and Weak Linkage 2.5.2 Sufficient Conditions for a Tournament to be k-Linked2.5.3 The Bermond-Thomassen Conjecture for Tournaments 2.6 Hamiltonian Paths and Cycles 2.6.1 Redei's Theorem 2.6.2 Hamiltonian Connectivity 2.6.3 Hamiltonian Cycles Containing or Avoiding Prescribed Arcs 2.7 Oriented Subgraphs of Tournaments 2.7.1 Transitive Subtournaments 2.7.2 Oriented Paths in Tournaments 2.7.3 Oriented Cycles in Tournaments 2.7.4 Trees in Tournaments 2.7.5 Largest n-Unavoidable Digraphs 2.7.6 Generalization to k-Chromatic Digraphs 2.8 Vertex-Partitions of Semicomplete Digraphs 2.8.1 2-Partitions into Strong Semicomplete Digraphs2.8.2 Partition into Highly Strong Subtournaments 2.8.3 2-Partitions With Prescribed Minimum Degrees 2.8.4 2-Partitions with Restrictions Both Inside and Between Sets 2.8.5 Partitioning into Transitive Tournaments 2.9 Feedback Sets 2.9.1 Feedback Vertex Sets 2.9.2 Feedback Arc Sets 2.9.3 FPT Algorithms for Feedback vertex set in tournaments 2.9.4 FPT Algorithms for Feedback arc set in tournaments 2.10 Small Certicates for k-(Arc)-Strong Connectivity 2.11 Increasing Connectivity by Adding or Reversing Arcs 2.12 Arc-Disjoint Spanning Subdigraphs of Semicomplete Digraphs2.12.1 Arc-Disjoint Hamiltonian Paths and Cycles 2.12.2 Arc-Disjoint Spanning Strong Subdigraphs 2.12.3 Arc-Disjoint In- and Out-Branchings 2.13 Minors of Semicomplete Digraphs 2.14 Miscellaneous Topics 2.14.1 Arc-Pancyclicity 2.14.2 Critically k-Strong Tournaments 2.14.3 Subdivisions and Linkages 3. Acyclic Digraphs 3.1 Acyclic Orderings and Longest and Shortest Paths 3.2 Transitive Acyclic Digraphs 3.3 Out-branchings and in-branchings 3.3.1 Extremal number of leaves 3.3.2 Bounded out-degrees