Some upper bounds for 3-rainbow index of graphs

Abstract: A tree

T

, in an edge-colored graph

G

, is called {em a rainbow tree} if no two edges of

T

are assigned the same color. A {em

k

-rainbow coloring}of

G

is an edge coloring of

G

having the property that for every set

S

of

k

vertices of

G

, there exists a rainbow tree

T

in

G

such that

S s u b s e t e q V (T)

. The minimum number of colors needed in a

k

-rainbow coloring of

G

is the {em

k

-rainbow index of

G

}, denoted by

r x_{k} (G)

. In this paper, we consider 3-rainbow index

r x_{3} (G)

of

G

. We first show that for connected graph

G

with minimum degree

d e l t a (G) g e q 3

, the tight upper bound of

r x_{3} (G)

is

r x_{3} (G [D]) + 4

, where

D

is the connected 2-dominating set of

G

. And then we determine a tight upper bound for

K_{s, t} (3 l e q s l e q t)

and a better bound for

(P_{5}, C_{5})

-free graphs. Finally, we obtain a sharp bound for 3-rainbow index of general graphs.

Recommendations

Cited In (6)

This page was built for publication: Some upper bounds for 3-rainbow index of graphs