Article ID Journal Published Year Pages File Type
4649957 Discrete Mathematics 2008 6 Pages PDF
Abstract

If xx is a vertex of a digraph DD, then we denote by d+(x)d+(x) and d−(x)d−(x) the outdegree and the indegree of xx, respectively. The global irregularity of a digraph DD is defined by ig(D)=maxx∈V(D){d+(x),d−(x)}−miny∈V(D){d+(y),d−(y)}. If ig(D)=0ig(D)=0, then DD is regular and if ig(D)≤1ig(D)≤1, then DD is called almost regular.A cc-partite tournament is an orientation of a complete cc-partite graph. Recently, Volkmann and Winzen [L. Volkmann, S. Winzen, Almost regular cc-partite tournaments contain a strong subtournament of order cc when c≥5c≥5, Discrete Math. (2007), http://dx.doi.org/10.1016/j.disc.2006.10.019] showed that every almost regular cc-partite tournament DD with c≥5c≥5 contains a strongly connected subtournament of order pp for every p∈{3,4,…,c}p∈{3,4,…,c}. In this paper for the class of regular multipartite tournaments we will consider the more difficult question for the existence of strong subtournaments containing a given vertex. We will prove that each vertex of a regular multipartite tournament DD with c≥7c≥7 partite sets is contained in a strong subtournament of order pp for every p∈{3,4,…,c−4}p∈{3,4,…,c−4}.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,