Article ID Journal Published Year Pages File Type
419706 Discrete Applied Mathematics 2009 5 Pages PDF
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)(2k−1)-strong locally semicomplete digraph on at least 2k+12k+1 vertices contains a kk-strong spanning local tournament and prove the conjecture for k=1,2k=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−12k−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−32k−3.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,