Back to Search Start Over

k-strong spanning local tournaments in locally semicomplete digraphs

Authors :
Jørgen Bang-Jensen
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.

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