Some results on the 3-vertex-rainbow index of a graph (Q2021678)

In this paper, the authors investigate the 3-vertex-rainbow index \(rvx_3\) of unicyclic graphs and complementary graphs, respectively. Initially, they calculate 3-vertex-rainbow index \(rvx_3\) of a cycle \(C_n\). Theorem: For an integer \(n\), \[ r v x_{3}\left(C_{n}\right)= \begin{cases}0 & \text { if } \quad 3 \leq n \leq 4; \\ n-4 & \text { if } \quad n \geq 5.\end{cases} \] In the next result, it is proved that if \(G\) is a unicyclic graph of order \(n \geq 4\) that is not a cycle and the girth \(g(G) \in \{3,4\}\), then \(rvx_3(G) \leq n - 3\), and further it is proved that this bound is tight. Similarly, two more results are proved dealing with unicyclic graphs having girth 5 and girth at least 6. In fact, the following results are proved. Theorem: If \(G\) is a unicyclic graph of order \(n \geq 6\) that is not a cycle and girth \(5\), then \(rvx_3(G) \leq n - 4\), and the bound is tight. Theorem: If \(G\) is a unicyclic graph of order \(n \geq 7\) that is not a cycle and girth at least \(6\), then \(rvx_3(G) \leq n - 5\), and the bound is tight. Lastly, they investigate the 3-vertex-rainbow index of a connected graph \(G\) using the complement \(\bar{G}\) of \(G\) with diameter at least 3. Theorem: Let \(G\) be a connected graph of order \(n\). \par (i) If \(\bar{G}\) is connected and diam \((\bar{G}) \geq 4\), then \(r v x_{3}(G)=1\). \par (ii) If \(\bar{G}\) is connected and \(\operatorname{diam}(\bar{G})=3\), then \(1 \leq r v x_{3}(G) \leq 2\), and the bounds are tight. \par (iii) If \(\bar{G}\) is disconnected, then \(0 \leq r v x_{3}(G) \leq 1\), and the bounds are tight.