Can I read On the number of non-critical vertices in strong tournaments of order N with minimum out-degree δ+ and in-degree δ− on EtoBox?

On the number of non-critical vertices in strong tournaments of order N with minimum out-degree δ+ and in-degree δ− by S.V. Savchenko is a Computer Science article available to read on EtoBox.

What is On the number of non-critical vertices in strong tournaments of order N with minimum out-degree δ+ and in-degree δ− about?

Let T be a strong tournament of order n ≥ 4 with given minimum out-degree δ + and indegree δ -. By definition, a vertex w in T is non-critical if the subtournament Tw is also strong. In the present paper, we show that T contains at least min{n, 2δ + + 2δ - -2} noncritical vertices, and all tournaments for which this lower bound is attained are determined. For the case min{δ + , δ - } ≥ 2, we also describe all strong tournaments of order n ≥ 2δ + + 2δ -that include exactly 2δ + + 2δ - -1 non-critical vertices. From this description it follows that any strong tournament T of order n ≥ 2δ + + 2δ - + 2 with min{δ + , δ - } ≥ 2 contains at least 2δ + + 2δ -non-critical vertices. Finally, for the case min{δ + , δ - } ≥ 4, we completely describe all strong tournaments of order n ≥ 2δ + + 2δ - + 2 that admit exactly 2δ + + 2δ -non-critical vertices. All of these results sharpen those obtained recently by K. Kotani in terms of δ = min{δ + , δ - }.

Who reads On the number of non-critical vertices in strong tournaments of order N with minimum out-degree δ+ and in-degree δ−?

Author

S.V. Savchenko

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0012-365X)

Published

2010

Language

EN

Field

Computer Science (Physical Sciences)