Generalized paths and cycles in semicomplete multipartite digraphs

DOI10.1016/J.DAM.2025.08.021MaRDI QIDQ6927977zbMATH OpenFDO

Authors Jørgen Bang-Jensen, A. Yeo

Publication date 17 September 2025

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

Full work available at URL https://doi.org/10.1016/J.DAM.2025.08.021

zbMATH Keywords

\(\{0, 1\}\)-TSP problemgeneralized cycleHamiltonian cycles avoiding arcsNP-completenessoutpathsquasi-Hamiltonian cyclesemicomplete multipartite digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Cites work

• A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
• A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian
• Arc-disjoint spanning sub(di)graphs in digraphs
• Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
• Cycles and paths in bipartite tournaments with spanning configurations
• Digraphs
• Finding a Longest Path in a Complete Multipartite Digraph
• Hamiltonian cycles avoiding prescribed arcs in semicomplete digraphs
• Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments
• Hamiltonian dicycles avoiding prescribed arcs in tournaments
• Hamiltonian-connected tournaments
• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• scientific article; zbMATH DE number 3859163 (Why is no real title available?)
• scientific article; zbMATH DE number 4047757 (Why is no real title available?)
• scientific article; zbMATH DE number 4103112 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3013308 (Why is no real title available?)
• One-diregular subgraphs in semicomplete multipartite digraphs
• Outpaths in semicomplete multipartite digraphs
• Outpaths of all lengths of an arc in regular multipartite tournaments
• Outpaths of arcs in almost regular multipartite tournaments
• Outpaths of arcs in multipartite tournaments
• Outpaths of arcs in regular 3-partite tournaments
• Quasi-Hamiltonian cycles in k-strong multipartite tournaments
• Quasi-hamiltonian paths in semicomplete multipartite digraphs
• Strongly quasi-Hamiltonian-connected semicomplete multipartite digraphs
• Weakly quasi-Hamiltonian-connected multipartite tournaments
• Weakly quasi-Hamiltonian-set-connected multipartite tournaments

Cited in

(2)

• Locally semicomplete multipartite digraphs: a generalization of both locally semicomplete digraphs and semicomplete multipartite digraphs
• The complexity of color-constrained paths in semicomplete multipartite digraphs

This page was built for publication: Generalized paths and cycles in semicomplete multipartite digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6927977)