Quasi‐transitive digraphs

DOI10.1002/jgt.3190200205zbMath0832.05048OpenAlexW1977215568MaRDI QIDQ4852401

Jing Huang, Jörgen Bang-Jensen

Publication date: 8 February 1996

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190200205

zbMATH Keywords

characterizationsdigraphpathtournamentspolynomial algorithmspancyclicityhamiltonian cyclequasi-transitive digraphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (52)

Infinite quasi-transitive digraphs with domination number 2 ⋮ Orientations of digraphs almost preserving diameter ⋮ Action graph of a semigroup act & its functorial connection ⋮ Hamiltonian paths in \(k\)-quasi-transitive digraphs ⋮ Non-Critical Vertices and Long Circuits in Strong Tournaments of Order n and Diameter d ⋮ Vertex heaviest paths and cycles in quasi-transitive digraphs ⋮ On \(k\)-strong and \(k\)-cyclic digraphs ⋮ Paths and cycles in extended and decomposable digraphs ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ Colourings, homomorphisms, and partitions of transitive digraphs ⋮ Arc-Disjoint Paths in Decomposable Digraphs ⋮ Extended path partition conjecture for semicomplete and acyclic compositions ⋮ Vertex-pancyclism in the generalized sum of digraphs ⋮ \(k\)-quasi-transitive digraphs of large diameter ⋮ On the existence and number of (\(k+1\))-kings in \(k\)-quasi-transitive digraphs ⋮ Semicomplete compositions of digraphs ⋮ k‐quasi‐transitive digraphs of large diameter ⋮ Semi-strict chordal digraphs ⋮ Packing strong subgraph in digraphs ⋮ Independent sets and non-augmentable paths in generalizations of tournaments ⋮ Heroes in oriented complete multipartite graphs ⋮ Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs ⋮ Disjoint quasi-kernels in digraphs ⋮ \(k\)-colored kernels ⋮ \(k\)-kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs ⋮ On the complexity of the 3-kernel problem in some classes of digraphs ⋮ The second neighbourhood for bipartite tournaments ⋮ Minimum cycle factors in quasi-transitive digraphs ⋮ \(k\)-distinct in- and out-branchings in digraphs ⋮ Kernels by monochromatic paths in \(m\)-colored unions of quasi-transitive digraphs ⋮ On the structure of strong 3-quasi-transitive digraphs ⋮ Finding cheapest cycles in vertex-weighted quasi-transitive and extended semicomplete digraphs ⋮ Chordality of locally semicomplete and weakly quasi-transitive digraphs ⋮ Longest path partitions in generalizations of tournaments ⋮ Kernels in quasi-transitive digraphs ⋮ The second neighbourhood for quasi-transitive oriented graphs ⋮ On the existence of \((k,l)\)-kernels in infinite digraphs: a survey ⋮ Digraphs with proper connection number two ⋮ Supereulerian digraphs with given local structures ⋮ Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs ⋮ Some sufficient conditions for the existence of kernels in infinite digraphs ⋮ Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs ⋮ The structure of strong arc-locally semicomplete digraphs ⋮ Vertex deletion and cycles in multipartite tournaments ⋮ Weakly Hamiltonian-connected ordinary multipartite tournaments ⋮ Linkages in locally semicomplete digraphs and quasi-transitive digraphs ⋮ Tournaments and Semicomplete Digraphs ⋮ Quasi-Transitive Digraphs and Their Extensions ⋮ Lexicographic Orientation Algorithms ⋮ Kings in quasi-transitive digraphs ⋮ Sufficient Conditions for a Digraph to be Supereulerian ⋮ Disjoint Paths in Decomposable Digraphs

Cites Work

• Unnamed Item
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Hamiltonian-connected tournaments
• On \(k\)-strong and \(k\)-cyclic digraphs
• Kings in quasi-transitive digraphs
• On the structure of local tournaments
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs

This page was built for publication: Quasi‐transitive digraphs