Quasi-Transitive Digraphs and Their Extensions

DOI10.1007/978-3-319-71840-8_8zbMath1407.05106MaRDI QIDQ3120440

Hortensia Galeana-Sánchez, César Hernández-Cruz

Publication date: 4 March 2019

Published in: Springer Monographs in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-71840-8_8

Mathematics Subject Classification ID

05C20: Directed graphs (digraphs), tournaments

Related Items

Unnamed Item, Semicomplete compositions of digraphs, \((H, k)\)-reachability in \(H\)-arc-colored digraphs, Pancyclicity in strong \(k\)-quasi-transitive digraphs of large diameter, Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs, Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs, \(k\)-quasi-transitive digraphs of large diameter, Packing strong subgraph in digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hamiltonian paths in \(k\)-quasi-transitive digraphs
• Colourings, homomorphisms, and partitions of transitive digraphs
• On the existence and number of (\(k+1\))-kings in \(k\)-quasi-transitive digraphs
• Expressive power of digraph solvability
• Finding kernels or solving SAT
• \(k\)-kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs
• \((k + 1)\)-kernels and the number of \(k\)-kings in \(k\)-quasi-transitive digraphs
• Some remarks on the structure of strong \(k\)-transitive digraphs
• Edge-disjoint paths in digraphs with bounded independence number
• Some results on 4-transitive digraphs
• Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs
• On the structure of strong 3-quasi-transitive digraphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• The directed subgraph homeomorphism problem
• Hamiltonian-connected tournaments
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• Distances in orientations of graphs
• Linkages in locally semicomplete digraphs and quasi-transitive digraphs
• On the complexity of hamiltonian path and cycle problems in certain classes of digraphs
• Vertex heaviest paths and cycles in quasi-transitive digraphs
• Paths and cycles in extended and decomposable digraphs
• Kings in quasi-transitive digraphs
• Orientations of digraphs almost preserving diameter
• Complexity of the directed spanning cactus problem
• The structure of strong arc-locally semicomplete digraphs
• Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
• Number of 4-kings in bipartite tournaments with no 3-kings
• The Path Partition Conjecture is true for some generalizations of tournaments
• \((k-1)\)-kernels in strong \(k\)-transitive digraphs
• \(k\)-quasi-transitive digraphs of large diameter
• Independent sets and non-augmentable paths in generalizations of tournaments
• Perfect graphs, kernels, and cores of cooperative games
• On the complexity of the 3-kernel problem in some classes of digraphs
• Finding cheapest cycles in vertex-weighted quasi-transitive and extended semicomplete digraphs
• Longest path partitions in generalizations of tournaments
• 4-transitive digraphs I: the structure of strong 4-transitive digraphs
• Underlying graphs of 3-quasi-transitive digraphs and 3-transitive digraphs
• Arc-Disjoint Paths in Decomposable Digraphs
• k-kernels in generalizations of transitive digraphs
• Disjoint quasi-kernels in digraphs
• Robbins's Theorem for Mixed Multigraphs
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Generalizations of tournaments: A survey
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
• 3-transitive digraphs
• On the number of quasi-kernels in digraphs
• Quasi‐transitive digraphs
• Digraphs with the path‐merging property
• k‐Kings in k‐Quasitransitive Digraphs
• Disjoint Paths in Decomposable Digraphs
• The directed path partition conjecture
• Digraphs
• Combinatorial optimization. Theory and algorithms