Rainbow vertex-connection number of 2-connected graphs

Details Rainbow vertex-connection number of 2-connected graphs Rainbow vertex-connection number of 2-connected graphs

2011-10-26

arxiv.org/abs/1110.5770v1

Mathematics

Combinatorics

10 pages

Scientific paper

The {\em rainbow vertex-connection number}, $rvc(G)$, of a connected graph $G$ is the minimum number of colors needed to color its vertices such that every pair of vertices is connected by at least one path whose internal vertices have distinct colors. In this paper we first determine the rainbow vertex-connection number of cycle $C_n$ of order $n\geq 3$, and then, based on it, prove that for any 2-connected graph $G$, $rvc(G)\leq rvc(C_n)$, giving a tight upper bound for the rainbow vertex-connection. As a consequence, we show that for a connected graph $G$ with a block decomposition $B_1, B_2, ..., B_k$ and $t$ cut vertices, $rvc(G)\leq rvc(B_1)+rvc(B_2)+ ... +rvc(B_k)+t$.

Affiliated with

Also associated with

No associations

Rating

Rainbow vertex-connection number of 2-connected graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rainbow vertex-connection number of 2-connected graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow vertex-connection number of 2-connected graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-717058