The Rainbow Vertex Connectivities of Small Cubic Graphs

Abstract

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 \leq k \leq \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.