The number of (C-3)over right arrow-free vertices on 3-partite tournaments

Abstract

Let T be a 3-partite tournament. We say that a vertex u is (C-3) over right arrow -free if v does not lie on any directed triangle of T. Let F-3 (T) be the set of the (C-3) over right arrow -free vertices in a 3-partite tournament and f(3)(T) its cardinality. In this paper we prove that if T is a regular 3-partite tournament, then F-3 (T) must be contained in one of the partite sets of T. It is also shown that for every regular 3-partite tournament, f(3)(T) does not exceed n/9, where n is the order of T. On the other hand, we give an infinite family of strongly connected tournaments having n - 4 (C-3) over right arrow -free vertices. Finally we prove that for every c >= 3 there exists an infinite family of strongly connected c-partite tournaments, D-c(T), with n - c 1 (C-3) over right arrow -free vertices. (C) 2010 Elsevier B.V. All rights reserved.