Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey

DOI10.1002/jgt.3190190405zbMath0839.05043OpenAlexW2143262036MaRDI QIDQ4842704

Gregory Gutin

Publication date: 18 June 1996

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

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

zbMATH Keywords

surveypathsHamiltoniancyclesindependent setpolynomial algorithmfactorHamiltonian cycle problemsemicomplete multipartite digraphsemicomplete bipartite digraphsextended semicomplete digraphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (34)

The cycle structure of regular multipartite tournaments ⋮ Almost regular multipartite tournaments containing a Hamiltonian path through a given arc ⋮ Hamiltonian paths containing a given arc, in almost regular bipartite tournaments ⋮ On cycles containing a given arc in regular multipartite tournaments ⋮ A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian ⋮ The number of kings in a multipartite tournament ⋮ Paths and cycles containing given arcs, in close to regular multipartite tournaments ⋮ On \(k\)-strong and \(k\)-cyclic digraphs ⋮ On cycles through a given vertex in multipartite tournaments ⋮ Alternating cycles and paths in edge-coloured multigraphs: A survey ⋮ Longest cycles in almost regular 3-partite tournaments ⋮ \(k\)-quasi-transitive digraphs of large diameter ⋮ Hamiltonian cycles in a generalization of bipartite tournaments with a cycle factor ⋮ Independent sets and non-augmentable paths in generalizations of tournaments ⋮ On optimal orientations of Cartesian products with a bipartite graph ⋮ Sufficient conditions for Hamiltonian cycles in bipartite digraphs ⋮ Multipartite tournaments: a survey ⋮ Vertex-disjoint cycles in bipartite tournaments ⋮ Almost regular \(c\)-partite tournaments contain a strong subtournament of order \(c\) when \(c\geqslant 5\) ⋮ When \(n\)-cycles in \(n\)-partite tournaments are longest cycles ⋮ On the connectivity of close to regular multipartite tournaments ⋮ The orientation number of two complete graphs with linkages ⋮ Cycles with a given number of vertices from each partite set in regular multipartite tournaments ⋮ On \(n\)-partite tournaments with unique \(n\)-cycle ⋮ Strong subtournaments containing a given vertex in regular multipartite tournaments ⋮ On a conjecture concerning the orientation number of a graph ⋮ Combinatorial optimization in system configuration design ⋮ Quasi-Hamiltonicity: A series of necessary conditions for a digraph to be Hamiltonian ⋮ All regular multipartite tournaments that are cycle complementary ⋮ Hamiltonian paths, containing a given path or collection of arcs, in close to regular multipartite tournaments ⋮ On optimal orientation of cycle vertex multiplications ⋮ Weakly Hamiltonian-connected ordinary multipartite tournaments ⋮ A note on the cardinality of certain classes of unlabeled multipartite tournaments ⋮ Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The radii of n-partite tournaments
• Weakly hamiltonian-connected vertices in bipartite tournaments
• Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament
• Cycles of Each Length in Regular Tournaments

This page was built for publication: Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey