Rainbow monochromatic k-edge-connection colorings of graphs

Abstract: A path in an edge-colored graph is called a monochromatic path if all edges of the path have a same color. We call

k

paths

P_{1}, c d o t s, P_{k}

rainbow monochromatic paths if every

P_{i}

is monochromatic and for any two

i e q j

,

P_{i}

and

P_{j}

have different colors. An edge-coloring of a graph

G

is said to be a rainbow monochromatic

k

-edge-connection coloring (or

R M C_{k}

-coloring for short) if every two distinct vertices of

G

are connected by at least

k

rainbow monochromatic paths. We use

r m c_{k} (G)

to denote the maximum number of colors that ensures

G

has an

R M C_{k}

-coloring, and this number is called the rainbow monochromatic

k

-edge-connection number. We prove the existence of

R M C_{k}

-colorings of graphs, and then give some bounds of

r m c_{k} (G)

and present some graphs whose

r m c_{k} (G)

reaches the lower bound. We also obtain the threshold function for

r m c_{k} (G (n, p)) g e q f (n)

, where

l f l o o r f r a c n 2 f l o o r > k g e q 1

.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: Rainbow monochromatic \(k\)-edge-connection colorings of graphs