Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649729 | Discrete Mathematics | 2009 | 11 Pages |
A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. A vertex of a strongly connected digraph is called a non-separating vertex if its removal preserves the strong connectivity of the digraph in question.In 1990, Bang-Jensen showed that a strongly connected local tournament does not have any non-separating vertices if and only if it is a directed cycle. Guo and Volkmann extended this result in 1994. They determined the strongly connected local tournament with exactly one non-separating vertex. In the first part of this paper we characterize the class of strongly connected local tournaments with exactly two non-separating vertices.In the second part of the paper we consider the following problem: Given a strongly connected local tournament DD of order nn with at least n+2n+2 arcs and an integer 3≤r≤n3≤r≤n. How many directed cycles of length rr exist in DD? For tournaments this problem was treated by Moon in 1966 and Las Vergnas in 1975. A reformulation of the results of the first part shows that we have characterized the class of strongly connected local tournaments with exactly two directed cycles of length n−1n−1. Among other things we show that DD has at least n−r+1n−r+1 directed cycles of length rr for 4≤r≤n−14≤r≤n−1 unless it has a special structure. Moreover, we characterize the class of local tournaments with exactly n−r+1n−r+1 directed cycles of length rr for 4≤r≤n−14≤r≤n−1 which generalizes a result of Las Vergnas.