Article ID Journal Published Year Pages File Type
4649926 Discrete Mathematics 2008 12 Pages PDF
Abstract

An orientation of a complete graph is a tournament, and an orientation of a complete cc-partite graph is a cc-partite tournament. 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)=max{d+(x),d-(x)}-min{d+(y),d-(y)}ig(D)=max{d+(x),d-(x)}-min{d+(y),d-(y)} over all vertices xx and yy of DD (including x=yx=y). If ig(D)=0ig(D)=0, then DD is regular and if ig(D)⩽1ig(D)⩽1, then DD is called almost regular.In 1999, L. Volkmann showed that, if DD is an almost regular cc-partite tournament with c⩾4c⩾4, then DD contains a strongly connected subtournament of order pp for every p∈{3,4,…,c-1}p∈{3,4,…,c-1} and he conjectured that this also holds for p=cp=c, if c⩾5c⩾5. In this paper, we settle this conjecture in affirmative.

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