Rainbow connection number and the number of blocks

Abstract: An edge-colored graph

G

is rainbow connected if every pair of vertices of

G

are connected by a path whose edges have distinct colors. The rainbow connection number

r c (G)

of

G

is defined to be the minimum integer

t

such that there exists an edge-coloring of

G

with

t

colors that makes

G

rainbow connected. For a graph

G

without any cut vertex, i.e., a 2-connected graph, of order

n

, it was proved that

r c (G) l e q l c e i l f r a c n 2 c e i l

and the bound is tight. In this paper, we prove that for a connected graph

G

of order

n

with cut vertices,

r c (G) l e q f r a c n + r - 1 2

, where

r

is the number of blocks of

G

with even orders, and the upper bound is tight. Moreover, we also obtain a tight upper bound for a bridgeless graph, i.e., a 2-edge-connected graph.

Cites Work

Cited In (1)

This page was built for publication: Rainbow connection number and the number of blocks