Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418327 | Discrete Applied Mathematics | 2014 | 8 Pages |
Abstract
The rainbow vertex-connection number , rvc(G)rvc(G), of a connected graph GG 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 prove that for a 2-connected graph GG of order nn, rvc(G)≤{⌈n/2⌉−2if n=3,5,9⌈n/2⌉−1if n=4,6,7,8,10,11,12,13 or 15⌈n/2⌉if n≥16 or n=14. The upper bound is tight since the cycle CnCn on nn vertices has its rvc(Cn)rvc(Cn) equal to this bound.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xueliang Li, Sujuan Liu,