On the number of cycles in local tournaments |
| |
Authors: | Dirk Meierling Lutz Volkmann |
| |
Institution: | Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany |
| |
Abstract: | 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 D of order n with at least n+2 arcs and an integer 3≤r≤n. How many directed cycles of length r exist in D? 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−1. Among other things we show that D has at least n−r+1 directed cycles of length r for 4≤r≤n−1 unless it has a special structure. Moreover, we characterize the class of local tournaments with exactly n−r+1 directed cycles of length r for 4≤r≤n−1 which generalizes a result of Las Vergnas. |
| |
Keywords: | Local tournament Number of cycles Cut vertex |
本文献已被 ScienceDirect 等数据库收录! |