THE RAINBOW VERTEX CONNECTIVITIES OF SMALL CUBIC GRAPHS

摘要

A vertex colored path is vertex-rainbow if its internal vertices have distinct colors. For a connected graph G with connectivity kappa(G) and an integer k with 1 <= k <= kappa(G), the rainbow vertex k-connectivity of G is the minimum number of colors required to color the vertices of G such that any two vertices of G are connected by k internally vertex disjoint vertex-rainbow paths. In this paper, we determine the rainbow vertex k-connectivities of all small cubic graphs of order 8 or less.