Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
From MaRDI portal
Publication:1045053
DOI10.1016/j.disc.2008.04.016zbMath1207.05067OpenAlexW2017541517WikidataQ123241392 ScholiaQ123241392MaRDI QIDQ1045053
Publication date: 15 December 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2008.04.016
Trees (05C05) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)
Related Items (5)
Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments ⋮ Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2 ⋮ Sparse Spanning $k$-Connected Subgraphs in Tournaments ⋮ Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs ⋮ Tournaments and Semicomplete Digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs
- Complementary cycles of all lengths in tournaments
- Powers of Hamilton cycles in tournaments
- Minimum cycle factors in quasi-transitive digraphs
- Hamiltonian dicycles avoiding prescribed arcs in tournaments
- Edge-disjoint in- and out-branchings in tournaments and related path problems
- Hamiltonian-connected tournaments
- A note on spanning local tournaments in locally semicomplete digraphs
- On complementary cycles in locally semicomplete digraphs
- Characterization of \((m,1)\)-transitive and \((3,2)\)-transitive semi- complete directed graphs
- Cycles in multipartite tournaments: Results and problems
- Antidirected Hamiltonian paths between specified vertices of a tournament
- Spanning local tournaments in locally semicomplete digraphs
- Making a tournament \(k\)-arc-strong by reversing or deorienting arcs.
- Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture
- Weakly Hamiltonian-connected ordinary multipartite tournaments
- Partitioning vertices of a tournament into independent cycles
- Minimal edge-coverings of pairs of sets
- On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
- Hardness of fully dense problems
- The Minimum Spanning Strong Subdigraph Problem for Extended Semicomplete Digraphs and Semicomplete Bipartite Digraphs
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Approximation Algorithms for Several Graph Augmentation Problems
- Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
- A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs
- A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
- A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
- Generalizations of tournaments: A survey
- Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments
- Adding and Reversing Arcs in Semicomplete Digraphs
- Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
- Finding an Oriented Hamiltonian Path in a Tournament
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- LOCALLY SEMICOMPLETE DIGRAPHS WITH A FACTOR COMPOSED OF k CYCLES
- An Algorithm for Submodular Functions on Graphs
- Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
- Digraphs with the path‐merging property
- Approximating the Minimum Equivalent Digraph
- A Polynomial Time Algorithm for Finding a Cycle Covering a Given Set of Vertices in a Semicomplete Multipartite Digraph
- Ranking Tournaments
- Optimum branchings
- Algorithms and Data Structures
- Aggregating inconsistent information
- Trees in tournaments
This page was built for publication: Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
