WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 12, 2013
On Two Variants of Rainbow Connection
Author:
Abstract: A vertex-colored graph G is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. A path P connecting two vertices u and v in a total-colored graph G is called a rainbow total-path between u and v if all elements in V(P) U E(P), except for u and v, are assigned distinct colors. The total-colored graph G is rainbow total-connected if it has a rainbow total-path between every two vertices. The rainbow total-connection number, denoted by rtc(G), of a graph G is the minimum colors such that G is rainbow total-connected. In this paper, we will obtain some results for these two variants of rainbow connection. For rainbow vertex-connection, we will first investigate the rainbow vertex-connection number of a graph according to some structural conditions of its complementary graph G. Next, we will investigate graphs with large rainbow vertex-connection numbers. We then derive a sharp upper bound for rainbow vertex-connection numbers of line graphs. For rainbow total- connection, we will determine the precise values for rainbow total-connection numbers of some special graph classes, including complete graphs, trees, cycles and wheels.
Search Articles
Keywords: vertex-coloring, total-coloring, rainbow vertex-connection number, rainbow total-connection number, rainbow connection number, complementary graph