The rainbow k-connectivity of two classes of graphs

Abstract: A path in an edge-colored graph

G

, where adjacent edges may be colored the same, is called a rainbow path if no two edges of

G

are colored the same. For a

k a p p a

-connected graph

G

and an integer

k

with

1 l e q k l e q k a p p a

, the rainbow

k

-connectivity

r c_{k} (G)

of

G

is defined as the minimum integer

j

for which there exists a

j

-edge-coloring of

G

such that every two distinct vertices of

G

are connected by

k

internally disjoint rainbow paths. Let

G

be a complete

(e l l + 1)

-partite graph with

e l l

parts of size

r

and one part of size

p

where

0 l e q p < r

(in the case

p = 0

,

G

is a complete

e l l

-partite graph with each part of size

r

). This paper is to investigate the rainbow

k

-connectivity of

G

. We show that for every pair of integers

k g e q 2

and

r g e q 1

, there is an integer

f (k, r)

such that if

e l l g e q f (k, r)

, then

r c_{k} (G) = 2

. As a consequence, we improve the upper bound of

f (k)

from

(k + 1)^{2}

to

c k^{3 / 2} + C

, where

0 < c < 1

,

C = o (k^{3 / 2})

, and

f (k)

is the integer such that if

n g e q f (k)

then

r c_{k} (K_{n}) = 2

.

Recommendations

Cited in

(16)

This page was built for publication: The rainbow $k$-connectivity of two classes of graphs