Back to Search
Start Over
k-strong spanning local tournaments in locally semicomplete digraphs
- Source :
- Discrete Applied Mathematics. (11):2536-2540
- Publisher :
- Elsevier B.V.
-
Abstract
- We point out mistakes in two papers previously published in Discrete Applied Mathematics, dealing with highly strongly connected spanning local tournaments in locally semicomplete digraphs. We conjecture that every (2k−1)-strong locally semicomplete digraph on at least 2k+1 vertices contains a k-strong spanning local tournament and prove the conjecture for k=1,2. We also prove that every 5-strong locally semicomplete digraph which is not semicomplete contains a 3-strong spanning local tournament. We furthermore show that for semicomplete digraphs, which form a proper subclass of locally semicomplete digraphs, 2k−1 would be the best possible bound and for locally semicomplete digraphs which are not semicomplete we show that the correct bound is at least 2k−3.
- Subjects :
- Discrete mathematics
Semicomplete digraph
Strongly connected component
Conjecture
Mathematics::Combinatorics
Applied Mathematics
Connectivity in digraphs
Digraph
Directed graph
Combinatorics
Computer Science::Discrete Mathematics
Discrete Mathematics and Combinatorics
Tournament
Local tournament
Locally semicomplete digraph
Connectivity
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Issue :
- 11
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....f1372e7a612fdba0c66340383616be23
- Full Text :
- https://doi.org/10.1016/j.dam.2009.03.012