Rainbow vertex connection number of some ladder-type graphs

Abstract

A vertex-coloured graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colours. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colours that are needed to make G, a rainbow vertex-connected. When sending messages in a cellular network, each link between two vertices is assigned a separate channel. The rainbow connection numbers are used to find the required minimum number of separate channels. In this work, rainbow connectivity numbers on some ladder-type graphs were considered. Ladder-type graphs can be categorized as simple Ladder graphs, Roach graphs, Circular ladder graphs, Triangular ladder graphs, Diagonal ladder graphs and Circular, triangular ladder graphs. Most research has been done on the rainbow vertex connectivity number of pencil graphs, wheel graphs, star graphs, a cartesian product of two graphs, etc. Only a few types of research were available in the literature about ladder and Mobius ladder graphs. In this study, a simple ladder graph and a Roach graph were considered and derived formulae for the rainbow connectivity number of those graphs. We obtained the rainbow vertex connection number of the ladder graph Ln with order 2n as n – 1 and rvc(G) of a Roach graph R (2n, 2k), when, n = 1, rvc(R(2n, 2k)) = k, and rvc(R(2n, 2k)) = 2n for n ≥ 2 and k = 2, ... , 2 + (n − 1) and rvc(R(2n, 2k) = k + (n − 1) for k ≥ 2 + n, n ≥ 2.