A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs

Authors

Abstract: Let

D

be a digraph. We define the minimum semi-degree of

D

as

d e l t a^{0} (D) := m i n d e l t a^{+} (D), d e l t a^{-} (D)

. Let

k

be a positive integer, and let

S = s

and

T = t_{1}, d o t s, t_{k}

be any two disjoint subsets of

V (D)

. A set of

k

internally disjoint paths joining source set

S

and sink set

T

that cover all vertices

D

are called a one-to-many

k

-disjoint directed path cover (

k

-DDPC for short) of

D

. A digraph

D

is semicomplete if for every pair

x, y

of vertices of it, there is at least one arc between

x

and

y

. In this paper, we prove that every semicomplete digraph

D

of sufficiently large order

n

with

d e l t a^{0} (D) g e q l c e i l (n + k - 1) / 2 c e i l

has a one-to-many

k

-DDPC joining any disjoint source set

S

and sink set

T

, where

S = s, T = t_{1}, d o t s, t_{k}

.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs