Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number of a graph

preprint2011arXivOpen access

Abstract

A vertex-colored graph GG is rainbow vertex-connected if any pair of distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of GG, denoted by rvc(G)rvc(G), is the minimum number of colors that are needed to make GG rainbow vertex-connected. In this paper we give a Nordhaus-Gaddum-type result of the rainbow vertex-connection number. We prove that when GG and Gˉ\bar{G} are both connected, then 2≤rvc(G)+rvc(Gˉ)≤n−12\leq rvc(G)+rvc(\bar{G})\leq n-1. Examples are given to show that both the upper bound and the lower bound are best possible for all n≥5n\geq 5.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.