On directed version of the Sauer-Spender Theorem

Publication date 31 January 2020

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let

D = (V, A)

be a digraph of order

n

and let

W

be any subset of

V

. We define the minimum semi-degree of

W

in

D

to be

d e l t a^{0} (W) = m b o x m i n d e l t a^{+} (W), d e l t a^{-} (W)

, where

d e l t a^{+} (W)

is the minimum out-degree of

W

in

D

and

d e l t a^{-} (W)

is the minimum in-degree of

W

in

D

. Let

k

be an integer with

k g e q 1

. In this paper, we prove that for any positive integer partition

| W | = s u m_{i = 1}^{k} n_{i}

with

n_{i} g e q 2

for each

i

, if

d e l t a^{0} (W) g e q f r a c 3 n - 3 4

, then there are

k

vertex disjoint cycles

C_{1}, l d o t s, C_{k}

in

D

such that each

C_{i}

contains exactly

n_{i}

vertices of

W

. Moreover, the lower bound of

d e l t a^{0} (W)

can be improved to

f r a c n 2

if

k = 1

, and

f r a c n 2 + | W | - 1

if

n g e q 2 | W |

. The minimum semi-degree condition

d e l t a^{0} (W) g e q f r a c 3 n - 3 4

is sharp in some sense and this result partially confirms the conjecture posed by Wang [Graphs and Combinatorics 16 (2000) 453-462]. It is also a directed version of the Sauer-Spender Theorem on vertex disjoint cycles in graphs [J. Combin. Theory B, 25 (1978) 295-302].

This page was built for publication: On directed version of the Sauer-Spender Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333860)