Classes of Directed Graphs (Springer Monographs in Mathematics)

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 Algorithms
2. 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-Linked
		2.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 Digraphs
		2.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 Digraphs
		2.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
	3.4 The k-Linkage problem
	3.5 Enumeration
	3.6 Maximum Dicuts
	3.7 Acyclic Subdigraphs
		3.7.1 Spanning Acyclic Subdigraphs
		3.7.2 Induced Acyclic Subgraphs
	3.8 The Multicut Problem
	3.9 Convex Sets and Embedded Computing
		3.9.1 Bounds for the Number of Connected Convex Sets
		3.9.2 Algorithm for Generating Convex Sets
	3.10 Out-forest-based Cryptographic Enforcement Schemes
		3.10.1 Optimal Key Allocation
		3.10.2 Optimal Spanning Out-forests
		3.10.3 Optimal Dipath Factors
	3.11  PERT/CPM in Project Scheduling
	3.12 One-sink Partitioning
	3.13 Acyclic edge-coloured graphs
4. Euler Digraphs
	4.1 Basic Constructions and Properties
		4.1.1 Cuts in Euler Digraphs
		4.1.2 Hardness Constructions
		4.1.3 Splitting Off and Other Operations
	4.2 Problems Regarding Euler Tours
	4.3 Euler Digraphs of Bounded Width
		4.3.1 Cutwidth and Bounded Pathwidth
	4.4 Cycle-Packing and Cycle-Hitting
		4.4.1 Feedback Arc Set
		4.4.2 Arc-Disjoint Cycles
		4.4.3 Additional Topics
	4.5 Linkages and Cut Problems
		4.5.1 Two-Commodity Flow
		4.5.2 General Arc-Disjoint Paths Problems
		4.5.3 Free Multiflow and Arc Multiway Cut
		4.5.4 General Integral Weighted Path Packings
5. Planar Digraphs
	5.1 Low Polynomial-Time Algorithms
		5.1.1 Warm-Up: Source also Lying on the Outer Face
		5.1.2 The Algorithm for the General Case
		5.1.3 Implementing a Single Step
		5.1.4 Bounding the Number of Steps
		5.1.5 Perspective
	5.2 The Disjoint Paths Problem
		5.2.1 Cohomology Equivalence and Feasibility
		5.2.2 Homology Equivalence and Duals
		5.2.3 Disjoint Paths in Directed Planar Graphs
		5.2.4 Fixed-Parameter Algorithm: Highlights
		5.2.5 Perspective
	5.3 Directed Grids
		5.3.1 Well-Linked Sets
		5.3.2 Eulerian Digraphs
		5.3.3 Cut-Matching Game
		5.3.4 Finding a Grid in an Eulerian Digraph
		5.3.5 Perspective
6. Locally Semicomplete Digraphs and Generalizations
	6.1 New Definitions
	6.2 The Path Merging Property
	6.3 The Structure of Non-strong Locally (In-)Semicomplete Digraphs
	6.4 Hamiltonian Paths and Cycles
		6.4.1 Hamilton Cycles in Path-Mergeable Digraphs
	6.5 Round Decomposable Digraphs
		6.5.1 Strong Round Decomposable Locally Semicomplete Digraphs
	6.6 Classification of Locally Semicomplete Digraphs
	6.7 Hamiltonian Connectivity
	6.8 Pancyclicity
	6.9 Cycle Factors with a Fixed Number of Cycles
	6.10 Arc-Disjoint Paths
	6.11 Vertex-Disjoint Paths
		6.11.1 Algorithmic Results
		6.11.2 Sufficient Conditions for Being k-Linked
	6.12  Arc-Disjoint Spanning Subdigraphs
	6.13 Kernels and Quasi-Kernels
	6.14 Feedback Sets in Locally Semicomplete Digraphs
		6.14.1 Feedback Vertex Sets
		6.14.2 Feedback Arc Sets
	6.15 Orientations of Locally Semicomplete Digraphs
		6.15.1 Diameter Preserving Orientations
		6.15.2 Highly Connected Orientations of Locally Semicomplete Digraphs
	6.16 Out-Round Digraphs
	6.17 Miscellaneous Topics
		6.17.1 Kings
		6.17.2 Cycle Extendability
		6.17.3 Pancyclic Arcs and Arc-Traceability
		6.17.4 Hamiltonicity of Digraphs with Degree Bounds on Certain Vertices
		6.17.5 The Directed Steiner Problem
7. Semicomplete Multipartite Digraphs
	7.1 Overview of Chapter 7
	7.2 Further Notation
	7.3 The Irreducible Cycle Subgraph Theorem
		7.3.1 An Outline of the Proof of Theorem 7.3.1
	7.4 Semicomplete Bipartite Digraphs
		7.4.1 Cycles in Semicomplete Bipartite Digraphs
		7.4.2 Even Pancyclic Bipartite Tournaments
		7.4.3 Paths in Semicomplete Bipartite Digraphs
	7.5 Paths in Semicomplete Multipartite Digraphs
		7.5.1 Hamilton Paths Containing Arcs
	7.6 Cycles in Semicomplete Multipartite Digraphs
		7.6.1 Pancyclicity
	7.7 Short Cycles in Semicomplete Multipartite Digraphs
	7.8 Regular and Close to Regular Semicomplete Multipartite Digraphs
		7.8.1 Connectivity in Close to Regular Semicomplete Multipartite Digraphs
		7.8.2 Pancyclicity in Close to Regular Semicomplete Multipartite Digraphs
	7.9 k-Strong Semicomplete Multipartite Digraphs
	7.10 Extended Semicomplete Digraphs
		7.10.1 Paths in Extended Semicomplete Digraphs
		7.10.2 Pancyclicity in Extended Semicomplete Digraphs
	7.11 Orientations
	7.12 Kings in Semicomplete Multipartite Digraphs
	7.13 Out-Paths in Semicomplete Multipartite Digraphs
	7.14 Quasi-Hamiltonian Paths in Semicomplete Multipartite Digraphs
	7.15 Strongly Connected Spanning Subgraphs with Minimum Number of Arcs
	7.16 k-Coloured Kernels in Arc-Coloured Semicomplete Multipartite Digraphs
	7.17 Complementary Cycles in Semicomplete Multipartite Digraphs
	7.18 Applications of Semicomplete Multipartite Digraphs
	7.19 Conjectures
8. Quasi-Transitive Digraphs and Their Extensions
	8.1 Introduction
		8.1.1 General Overview
		8.1.2 Chapter Overview
		8.1.3 Terminology and Notation
	8.2 Transitive Digraphs
	8.3 Structural Properties
		8.3.1 Quasi-Transitive Digraphs
		8.3.2 k-Quasi-Transitive Digraphs
		8.3.3 k-Transitive Digraphs
		8.3.4 Totally Φ-Decomposable Digraphs
	8.4 Hamiltonian, Longest and Vertex-Cheapest Paths and Cycles
		8.4.1 k-Transitive and k-Quasi-Transitive Digraphs
		8.4.2 Hamiltonian Cycles in quasi-transitive digraphs and Totally Φ-Decomposable Digraphs
		8.4.3 Vertex-Cheapest Paths and Cycles
		8.4.4 Minimum Cost k-Path-Cycle Subdigraphs
		8.4.5 Cheapest i-Path Subdigraphs in Quasi-Transitive Digraphs
		8.4.6 Finding a Cheapest Cycle in a Quasi-Transitive Digraph
	8.5 Linkages
		8.5.1 k-Linkages
		8.5.2 Weak k-Linkages
	8.6 Kings and Kernels
		8.6.1 Kings
		8.6.2 (k,ell)-Kernels
	8.7 The Path Partition Conjecture
		8.7.1 The Conjecture
		8.7.2 Known Results
	8.8 Miscellaneous
		8.8.1 Vertex Pancyclicity
		8.8.2 Acyclic Spanning Subgraphs
		8.8.3 Orientations of Digraphs Almost Preserving Diameter
		8.8.4 Sparse Subdigraphs with Prescribed Connectivity
		8.8.5 Arc-Disjoint In- and Out-Branchings
9. Digraphs of Bounded Width
	9.1 Introduction
	9.2 Tree-Width Inspired Width Measures
		9.2.1 Graph Searching Games
		9.2.2 Decompositions of Directed Graphs
		9.2.3 Tree-Width Based Digraph Width Measures
		9.2.4 Alternative Characterizations of Digraph Width Measures
		9.2.5 Comparing Directed Width Measures
	9.3 Structure Theory for Directed Graphs Based on Directed Minors
	9.4 Complexity of Directed Width Measures and Algorithmic Applications
		9.4.1 Complexity of Directed Width Measures
		9.4.2 Computing Directed Graph Decompositions
	9.5 Applications of Tree-Width Inspired Directed Width Measures
		9.5.1 Disjoint Paths and Linkage Problems in Digraphs of Bounded Width
		9.5.2 Linkages in General Digraphs
		9.5.3 The Erdős-Pósa Property for Directed Graphs
	9.6 Density Based Width Measures
		9.6.1 Directed Minors
		9.6.2 Width Measures Defined by Shallow Directed Minors and Bounded Edge Densities
	9.7 Classes of Directed Bounded Expansion
		9.7.1 Generalised Colouring Numbers
		9.7.2 Neighbourhood Complexity
		9.7.3 A Splitter Game for Classes of Digraphs of Bounded Expansion
		9.7.4 Neighbourhood Covers
		9.7.5 Constant-Factor Approximation Algorithms for Strong Dominating Sets
	9.8 Nowhere Crownful Classes of Digraphs
	9.9 Rank-Width Inspired Width Measures
		9.9.1 Directed Clique-Width
		9.9.2 Bi-Rank-Width and mathbbF4-Rank-Width
		9.9.3 Computing Rank-Decompositions
		9.9.4 Algorithmic Applications
		9.9.5 Vertex-Minors and Pivot-Minors
10. Digraphs Products
	10.1 The Four Standard Associative Products
	10.2 Distance
	10.3 Connectivity
	10.4 Neighborhoods, Kings and Kernels
	10.5 Hamiltonian Properties
	10.6 Invariants
	10.7 Quotients and Homomorphisms
	10.8 Cancellation
	10.9 Prime Factorization
	10.10 Cartesian Skeletons
	10.11 Prime Factorings of Direct and Strong Products
11. Miscellaneous Digraph Classes
	11.1 Introduction
	11.2 Line Digraphs
		11.2.1 Connectivity
		11.2.2 Diameter
		11.2.3 Kernels, Solutions and Generalizations
		11.2.4 Branchings
		11.2.5 Cycles and Trails
		11.2.6 mathcalNP-Complete Problems for Line-Digraphs
		11.2.7 Independence Number
		11.2.8 Chromatic Number
	11.3 Iterated Line Digraphs
		11.3.1 Connectivity
		11.3.2 Diameter
		11.3.3 Branchings
		11.3.4 (h,p)-Domination Number
		11.3.5 Cycles and Trails
		11.3.6 Independence Number
		11.3.7 Chromatic Number
	11.4 de Bruijn Digraphs
		11.4.1 Connectivity
		11.4.2 Diameter
		11.4.3 Branchings
		11.4.4 (h,p)-Domination Number
		11.4.5 Cycles and Trails
	11.5 Kautz Digraphs
		11.5.1 Connectivity
		11.5.2 Diameter
		11.5.3 Branchings
		11.5.4 (h,p)-Domination Number
		11.5.5 Cycles and Trails
	11.6 Directed Cographs
	11.7 Perfect Digraphs
	11.8 Arc-Locally Semicomplete Digraphs
	11.9 mathcalHi-Free Digraphs
12. Lexicographic Orientation Algorithms
	12.1 Introduction
	12.2 Algorithms for Π-Orientations
		12.2.1 Comparability Graphs
		12.2.2 Proper Circular Arc Graphs
		12.2.3 Proper Interval Graphs
		12.2.4 Interval Containment Bigraphs
	12.3 Orientation Completion Problems
		12.3.1 Quasi-transitive and Transitive Orientation Completions
		12.3.2 Local and Acyclic Local Tournament Orientation Completions
		12.3.3 Locally Transitive Local Tournament Orientation Completions
	12.4 Orientation Sandwich Completion Problems
Symbol Index
Author Index
Subject Index