Quasi-Transitive Digraphs and Their Extensions
From MaRDI portal
Publication:3120440
DOI10.1007/978-3-319-71840-8_8zbMath1407.05106OpenAlexW2808833857MaRDI 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
Related Items (8)
\(k\)-quasi-transitive digraphs of large diameter ⋮ Semicomplete compositions of digraphs ⋮ \((H, k)\)-reachability in \(H\)-arc-colored digraphs ⋮ Packing strong subgraph in digraphs ⋮ Pancyclicity in strong \(k\)-quasi-transitive digraphs of large diameter ⋮ Unnamed Item ⋮ 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
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
This page was built for publication: Quasi-Transitive Digraphs and Their Extensions
