Digraphs
From MaRDI portal
Publication:5502988
DOI10.1007/978-1-84800-998-1zbMath1170.05002OpenAlexW4240899876MaRDI QIDQ5502988
Gregory Gutin, Jörgen Bang-Jensen
Publication date: 12 January 2009
Published in: Springer Monographs in Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-84800-998-1
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)
Related Items
Disjoint Cycles in a Digraph with Partial Degree, Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach, Optimal orientations of vertex-multiplications of cartesian products of graphs, Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem, Ádám's conjecture, Characterizations and directed path-width of sequence digraphs, A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs, Semicomplete compositions of digraphs, Cycle selections, Results on the small quasi-kernel conjecture, Some α -spectral extremal results for some digraphs, \((H, k)\)-reachability in \(H\)-arc-colored digraphs, Frenetic steering in a nonequilibrium graph, Spanning eulerian subdigraphs in semicomplete digraphs, Principal components along quiver representations, On orientations maximizing total arc-connectivity, Proper‐walk connection number of graphs, k‐quasi‐transitive digraphs of large diameter, Good orientations of unions of edge‐disjoint spanning trees, Extremal total distance of graphs of given radius I, Forbidden subdigraphs conditions on the traceability conjecture, On the infinite Lucchesi–Younger conjecture I, The iterated local transitivity model for tournaments, Planar hypohamiltonian oriented graphs, Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties, Locally irregular edge-coloring of subcubic graphs, Complementary cycles of any length in regular bipartite tournaments, Spanning 3-strong tournaments in 5-strong semicomplete digraphs, Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2, Good acyclic orientations of 4‐regular 4‐connected graphs, Antidirected spanning closed trail in tournaments, Recognizing when a preference system is close to admitting a master list, Unnamed Item, Directed Steiner tree packing and directed tree connectivity, Complexity of (arc)-connectivity problems involving arc-reversals or deorientations, Vertex‐disjoint cycles of the same length in tournaments, Making a tournament k $k$‐strong, Ore conditions for antistrong digraphs, (Strong) proper vertex connection of some digraphs, Causality Modeling and Statistical Generative Mechanisms, The localization game on oriented graphs, Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm, Detours in directed graphs, Packing arc-disjoint cycles in oriented graphs, Edge-disjoint properly colored cycles in edge-colored complete graphs, Twin-distance-hereditary digraphs, 4-Free Strong Digraphs with the Maximum Size, Subeulerian oriented graphs, Extremal and Degree Conditions for Path Extendability in Digraphs, Disjoint cycles in tournaments and bipartite tournaments, Proper cycles and rainbow cycles in 2-triangle-free edge-colored complete graphs, On the influence of the interaction graph on a finite dynamical system, FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphs, Locating-dominating sets in local tournaments, A note on Seymour's second neighborhood conjecture, On Fixable Families of Boolean Networks, Antidirected Hamiltonian paths and cycles of digraphs with \(\alpha_2\)-stable number 2, Unique stable matchings, Sparse Spanning $k$-Connected Subgraphs in Tournaments, Inclusion matrices for rainbow subsets, Symmetric cores and extremal size bound for supereulerian semicomplete bipartite digraphs, Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs, Computing the fully optimal spanning tree of an ordered bipolar directed graph, Two Cases of Digraph Structures Corresponding to Minimal Positive Realisation of Fractional Continuous-Time Linear Systems of Commensurate Order, Unnamed Item, Unnamed Item, Unnamed Item, Kernels, truth and satisfaction, Consensus and Information Cascades in Game-Theoretic Imitation Dynamics with Static and Dynamic Network Topologies, Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments, A Dirac Type Condition for Properly Coloured Paths and Cycles, Component order connectivity in directed graphs, Efficient algorithms for measuring the funnel-likeness of DAGs, A note on the restricted arc connectivity of oriented graphs of girth four, Polynomial algorithms for canonical forms of orientations, Physically feasible decomposition of Engino® toy models: A graph-theoretic approach, Feedback edge sets in temporal graphs, Fuzzy k-Competition Graphs and p-Competition Fuzzy Graphs, Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs, Circular slider graphs: de Bruijn, Kautz, Rauzy, lamplighters and spiders, Finding a Set of (A, B, C, D) Realisations for Fractional One-Dimensional Systems with Digraph-Based Algorithm, Expansion of Digraph Size of 1-D Fractional System with Delay, Reduction of the small gain condition for large‐scale interconnections, Sufficient Conditions for a Digraph to be Supereulerian, Perfect Digraphs, New Constructions and Bounds for Winkler's Hat Game, Universal Logic as a Science of Patterns, Granular computing on basic digraphs, Cycle Transversals in Tournaments with Few Vertex Disjoint Cycles, Hierarchical subspace identification of directed acyclic graphs, Note on Perfect Forests in Digraphs, Partial Characterizations of 1‐Perfectly Orientable Graphs, Interpreting the basis path set in neural networks, The knapsack problem with special neighbor constraints, Every \((13k - 6)\)-strong tournament with minimum out-degree at least \(28k - 13\) is \(k\)-linked, On disjoint cycles of the same length in tournaments, Turán number of 3-free strong digraphs with out-degree restriction, The dichromatic polynomial of a digraph, Vertex-disjoint rainbow cycles in edge-colored graphs, Hamiltonian index of directed multigraph, Transversals of total strict linear orders, H-kernels by walks, The digrundy number of digraphs, Weakly reversible CF-decompositions of chemical kinetic systems, Enumerations of universal cycles for \(k\)-permutations, Arc reversals of cycles in orientations of \(G\) vertex-multiplications, Cycle extendability in extended tournaments, The smallest number of vertices in a 2-arc-strong digraph without pair of arc-disjoint in- and out-branchings, Minimally strong subgraph \((k,\ell ) \)-arc-connected digraphs, Games, graphs and Kirchhoff laws, Component order connectivity in directed graphs, A family of bipartite circulant tournaments with acyclic disconnection 3, Extended path partition conjecture for semicomplete and acyclic compositions, Compatible spanning circuits in edge-colored graphs, The second out-neighborhood for local tournaments, Analysis of the effect of medicines over bacteria based on competition graphs with picture fuzzy environment, Partitioning vertices into in- and out-dominating sets in digraphs, On the parameterized complexity of 2-partitions, Duality respecting representations and compatible complexity measures for gammoids, How to compute digraph width measures on directed co-graphs, On dominating pair degree conditions for Hamiltonicity in balanced bipartite digraphs, Proximity and remoteness in directed and undirected graphs, An analogue of Edmonds' branching theorem for infinite digraphs, \(H\)-kernels in unions of \(H\)-colored quasi-transitive digraphs, Restricted domination in quasi-transitive and 3-quasi-transitive digraphs, Matching and spanning trails in digraphs, Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs, A certifying and dynamic algorithm for the recognition of proper circular-arc graphs, On a problem of De Koninck, Efficient computation of the oriented chromatic number of recursively defined digraphs, Consecutive colouring of oriented graphs, The domination number of wrapped butterfly digraphs, Sufficient Ore type condition for a digraph to be supereulerian, On a stochastic approach to model the double phosphorylation/dephosphorylation cycle, Anti-Eulerian digraphs, A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs, 3-restricted arc connectivity of digraphs, The treewidth of proofs, A graph library for Isabelle, On characterizations for subclasses of directed co-graphs, The spectra of lifted digraphs, Diameter three orientability of bipartite graphs, On 1-factors with prescribed lengths in tournaments, Supereulerian 3-path-quasi-transitive digraphs, Oriented bipartite graphs and the Goldbach graph, Coevolutionary systems and PageRank, Outpaths of arcs in regular 3-partite tournaments, (Strong) total proper connection of some digraphs, Strong subgraph connectivity of digraphs, Mixed circular codes, Finding strongly connected components of simple digraphs based on granulation strategy, The domination number of round digraphs, On kernels by rainbow paths in arc-coloured digraphs, The antistrong property for special digraph families, 3-free strong digraphs with the maximum size, On supereulerian 2-edge-coloured graphs, The directed 2-linkage problem with length constraints, Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs, Hajós and Ore constructions for digraphs, Connectedness of digraphs from quadratic polynomials, Degree condition for a digraph to be supereulerian, On width measures and topological problems on semi-complete digraphs, Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles, Supereulerian digraphs with given diameter, A cooperative game for automated learning of elasto-plasticity knowledge graphs and models with AI-guided experimentation, Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs, Diffusion and consensus on weakly connected directed graphs, Comparing linear width parameters for directed graphs, Characterization of color patterns by dynamic \(H\)-paths, Complexity of some arc-partition problems for digraphs, Spanning acyclic subdigraphs and strong \(t\)-panconnectivity of tournaments, An algebraic approach to lifts of digraphs, Structural aspects of semigroups based on digraphs, Smallest number of vertices in a 2-arc-strong digraph without good pairs, Bounds on the \(k\)-restricted arc connectivity of some bipartite tournaments, Estimations of means and variances in a Markov linear model, On the complexity of singly connected vertex deletion, Some conditions for the existence of Euler \(H\)-trails, Disjoint properly colored cycles in edge-colored complete bipartite graphs, Idiosynchromatic poetry, Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks, Some transport and diffusion processes on networks and their graph realizability, Non-separating spanning trees and out-branchings in digraphs of independence number 2, Destroying longest cycles in graphs and digraphs, On connectivities of edge-colored graphs, Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs, Constructing the basis path set by eliminating the path dependency, \(\alpha\)-diperfect digraphs, Restricted cycle factors and arc-decompositions of digraphs, \(H\)-cycles in \(H\)-colored multigraphs, The extremal sizes of arc-maximal \((k, \ell)\)-digraphs, Extremal results for directed tree connectivity, Some results on the existence of Hamiltonian cycles in the generalized sum of digraphs, Completions of Leavitt path algebras., Explicit formulae for limit periodic flows on networks, Statistical mechanics of ontology based annotations, On Browder's convergence theorem and Halpern iteration process for \(G\)-nonexpansive mappings in Hilbert spaces endowed with graphs, Finding good 2-partitions of digraphs. I. Hereditary properties, On the lower bound of \(k\)-maximal digraphs, The complexity of finding arc-disjoint branching flows, Rural postman parameterized by the number of components of required edges, On pancyclic arcs in hypertournaments, Dichromatic polynomial of product digraphs, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, Intuitionistic fuzzy competition graphs, Parameterized algorithms for non-separating trees and branchings in digraphs, Parameterized complexity of the \(k\)-arc Chinese postman problem, Antistrong digraphs, Multiaspect graphs: algebraic representation and algorithms, Generalized network transport and Euler-Hille formula, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, The complexity of multicut and mixed multicut problems in (di)graphs, Parameterized complexity of \(k\)-Chinese postman problem, Weak expansion properties and large deviation principles for expanding Thurston maps, Connectivity of some algebraically defined digraphs, Vertex-disjoint directed and undirected cycles in general digraphs, Game-perfect digraphs, A linear bound towards the traceability conjecture, The complexity of two graph orientation problems, Hypohamiltonian oriented graphs of all possible orders, Triangle-free oriented graphs and the traceability conjecture, Decomposing locally semicomplete digraphs into strong spanning subdigraphs, On making directed graphs transitive, On spanning galaxies in digraphs, Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs, Exploiting hidden structure in selecting dimensions that distinguish vectors, The representation polyhedron of a semiorder., Vertex disjoint 4-cycles in bipartite tournaments, A probabilistic approach to problems parameterized above or below tight bounds, On the acyclic disconnection of multipartite tournaments, Locally dense supereulerian digraphs, Directed NLC-width, Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs, Notes on the deficiency-one theorem: multiple linkage classes, Quasi-hamiltonian paths in semicomplete multipartite digraphs, Out-degree reducing partitions of digraphs, Arc-disjoint spanning sub(di)graphs in digraphs, Cartesian product digraphs with optimal restricted arc connectivity, \(k\)-colored kernels, Arc-disjoint Hamiltonian cycles in round decomposable locally semicomplete digraphs, Properly colored paths and cycles, An algorithm for finding input-output constrained convex sets in an acyclic digraph, Pancyclic out-arcs of a vertex in oriented graphs, The second neighbourhood for bipartite tournaments, Stochastic stability in one-way flow networks, Hamilton cycles in dense vertex-transitive graphs, A new algorithm for finding trees with many leaves, Making a tournament \(k\)-arc-strong by reversing or deorienting arcs., Controllability of weighted and directed networks with nonidentical node dynamics, Zero forcing in iterated line digraphs, Asymptotic behaviour of flows on reducible networks, Group pinning consensus under fixed and randomly switching topologies with acyclic partition, Effects of adding a reverse edge across a stem in a directed acyclic graph, A spectral excess theorem for normal digraphs, Properly colored cycles in edge-colored complete graphs without monochromatic triangle: a vertex-pancyclic analogous result, Symmetric core and spanning trails in directed networks, Cycles through an arc in regular 3-partite tournaments, Rainbow connection in some digraphs, The dichromatic number of infinite families of circulant tournaments, Odd properly colored cycles in edge-colored graphs, Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials, Pairings and related symmetry notions, The entropy method for reaction-diffusion systems without detailed balance: first order chemical reaction networks, Chinese postman problem on edge-colored multigraphs, Strongly connected multivariate digraphs, Berge's conjecture and Aharoni-Hartman-Hoffman's conjecture for locally in-semicomplete digraphs, Oriented coloring on recursively defined digraphs, FPT algorithms for connected feedback vertex set, Expansive automata networks, \(k\)-strong spanning local tournaments in locally semicomplete digraphs, Vertex-disjoint cycles in local tournaments, Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs in tournaments, Spanning 2-strong tournaments in 3-strong semicomplete digraphs, A note on the relationship between graphs and information protocols, Quality analysis in acyclic production networks, Local tournaments with the minimum number of Hamiltonian cycles or cycles of length three, A random intersection digraph: indegree and outdegree distributions, What is on his mind?, The complexity of colouring by locally semicomplete digraphs, The complexity of locally injective homomorphisms, Degree constrained 2-partitions of semicomplete digraphs, On the most imbalanced orientation of a graph, Minimal positive realizations of linear continuous-time fractional descriptor systems: two cases of an input-output digraph structure, The second neighbourhood for quasi-transitive oriented graphs, Maximum matchings of a digraph based on the largest geometric multiplicity, Binary linear programming solutions and non-approximability for control problems in voting systems, Infinite families of 2-hypohamiltonian/2-hypotraceable oriented graphs, Disjoint directed and undirected paths and cycles in digraphs, The structure of strong arc-locally semicomplete digraphs, Minimum leaf out-branching and related problems, Vertex alternating-pancyclism in 2-edge-colored generalized sums of graphs, Parameterized complexity of candidate control in elections and related digraph problems, Indiscernibility structures induced from function sets : Graph and digraph case, A degree sum condition for Hamiltonicity in balanced bipartite digraphs, Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time, Finding good 2-partitions of digraphs. II. Enumerable properties, Acyclicity in edge-colored graphs, Disjoint dijoins for classes of dicuts in finite and infinite digraphs, Independent, Incidence Independent and Weakly Reversible Decompositions of Chemical Reaction Networks, Even circuits in oriented matroids, Unnamed Item, Bounds for the dichromatic number of a generalized lexicographic product of digraphs, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Digraph of the full transformation semigroup, On d-Fibonacci digraphs, On the Existence of Identifiable Reparametrizations for Linear Compartment Models, Arc-Disjoint Paths in Decomposable Digraphs, On random digraphs and cores, On the Most Imbalanced Orientation of a Graph, Fixed point theorems for multivalued nonself \(G\)-almost contractions in Banach spaces endowed with graphs, Arc-Disjoint In- and Out-Branchings With the Same Root in Locally Semicomplete Digraphs, Alternating-pancyclism in 2-edge-colored graphs, Cycle extension in edge-colored complete graphs, Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization, Rainbow antistrong connection in tournaments, On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks, Trail-connected tournaments, Arc-disjoint Hamiltonian paths in non-round decomposable local tournaments, Vertex-pancyclism in the generalized sum of digraphs, Packing arc-disjoint cycles in tournaments, PO-MOESP subspace identification of directed acyclic graphs with unknown topology, Notes on weak-odd edge colorings of digraphs, Every 8-traceable oriented graph is traceable, Minimum cuts of distance-regular digraphs, Disproof of a conjecture of Neumann-Lara, Kinetic Models in Natural Sciences, \(k\)-quasi-transitive digraphs of large diameter, A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs, Upward Planarity Testing of Embedded Mixed Graphs, Competition graphs under interval-valued \(m\)-polar fuzzy environment and its application, Properly colored 2-factors of edge-colored complete bipartite graphs, Degree-constrained 2-partitions of graphs, Unnamed Item, Structure of cycles in minimal strong digraphs, Unions of digraphs which become kernel perfect, Proper orientation, proper biorientation and semi-proper orientation numbers of graphs, Restricted arc connectivity of unidirectional hypercubes and unidirectional folded hypercubes, Dependency and accuracy measures for directed graphs, A generalization of properly colored paths and cycles in edge-colored graphs, Equivalences among five game specifications, including a new specification whose nodes are sets of past choices, A Result on Polynomials Derived Via Graph Theory, Onk-Maximal Strength Digraphs, Packing strong subgraph in digraphs, Oriented diameter of graphs with given girth and maximum degree, The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties, Edgewise strongly shellable clutters, On the problem of finding disjoint cycles and dicycles in a digraph, On the existence of the positive steady states of weakly reversible deficiency-one mass action systems, Partition and disjoint cycles in digraphs, (Arc-)disjoint flows in networks, Upward and quasi-upward planarity testing of embedded mixed graphs, Unnamed Item, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, Necessary and sufficient conditions for circulant digraphs to be antistrong, weakly-antistrong and anti-Eulerian, Hadwiger's Conjecture for ℓ‐Link Graphs, Unnamed Item, Arc-disjoint paths and trees in 2-regular digraphs, Method for Finding a set of (A,B,C,D) Realizations for Single-Input Multiple-Output / Multiple-Input Single-Output One-dimensional, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs, Walks: A Beginner's Guide to Graphs and Matrices, The structure of 4‐strong tournaments containing exactly three out‐arc pancyclic vertices, Unnamed Item, Cryptographic Enforcement of Information Flow Policies Without Public Information, A spectral excess theorem for digraphs with normal Laplacian matrices, Supereulerian Digraphs with Large Arc-Strong Connectivity, A semi-strong perfect digraph theorem, DAG-Width and Circumference of Digraphs, Covering Intersecting Bi-set Families under Matroid Constraints, Packing Arc-Disjoint Cycles in Tournaments, Unnamed Item, Arc-Disjoint Directed and Undirected Cycles in Digraphs, Unnamed Item, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, A Probabilistic Approach to Problems Parameterized above or below Tight Bounds, Unnamed Item, BOOLEAN DELAY EQUATIONS ON NETWORKS IN ECONOMICS AND THE GEOSCIENCES, Basic Terminology, Notation and Results, Tournaments and Semicomplete Digraphs, Acyclic Digraphs, Euler Digraphs, Locally Semicomplete Digraphs and Generalizations, Semicomplete Multipartite Digraphs, Quasi-Transitive Digraphs and Their Extensions, Miscellaneous Digraph Classes, Disjoint sub(di)graphs in digraphs, Some results on the existence of Hamiltonian cycles in -compositions of bipartite digraphs, Orientation Ramsey Thresholds for Cycles and Cliques, Results on uniquely colorable digraphs, On the number of reachable pairs in a digraph, Balanced branchings in digraphs, On the complexity of the misère version of three games played on graphs