Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs

DOI10.1016/0012-365X(93)E0195-AzbMath0839.05042MaRDI QIDQ1894766

Gregory Gutin

Publication date: 18 June 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(93)e0195-a

zbMATH Keywords

characterization; independent set; polynomial algorithms; semicomplete multipartite digraph; quasi-transitive digraphs; extended semicomplete digraphs

Mathematics Subject Classification ID

05C38: Paths and cycles

05C75: Structural characterization of families of graphs

05C20: Directed graphs (digraphs), tournaments

Related Items

Semicomplete compositions of digraphs, Hamiltonicity, pancyclicity, and full cycle extendability in multipartite tournaments, Pancyclic out-arcs of a vertex in oriented graphs, Minimum cycle factors in quasi-transitive digraphs, Linkages in locally semicomplete digraphs and quasi-transitive digraphs, Paths and cycles in extended and decomposable digraphs, Alternating cycles and paths in edge-coloured multigraphs: A survey, Sufficient conditions for a balanced bipartite digraph to be even pancyclic, Cycle extendability in extended tournaments, Multipartite tournaments: a survey, Vertex-pancyclism in the generalized sum of digraphs, Semicomplete Multipartite Digraphs, Quasi-Transitive Digraphs and Their Extensions

Cites Work

• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Cycles and paths of many lengths in bipartite digraphs
• Cycles in bipartite tournaments
• On cycles in multipartite tournaments
• Cycles and paths in bipartite tournaments with spanning configurations
• Weakly Hamiltonian-connected ordinary multipartite tournaments
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item