The vertex-rainbow index of a graph

DOI10.7151/DMGT.1887zbMATH Open1339.05056arXiv1502.00151OpenAlexW2963903543MaRDI QIDQ726646FDOQ726646

Authors: Yaping Mao 

Publication date: 13 July 2016

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: The $k$-rainbow index $r{x}_k(G)$ of a connected graph $G$ was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the $k$-rainbow index, we introduced the concept of $k$-vertex-rainbow index $rv{x}_k(G)$ in this paper. For a graph $G=(V,E)$ and a set $SsubseteqV$ of at least two vertices, emph{an $S$-Steiner tree} or emph{a Steiner tree connecting $S$} (or simply, emph{an $S$-tree}) is a such subgraph $T=(V^{\prime },E^{\prime })$ of $G$ that is a tree with $Ssubseteq{V}^{\prime }$. For $SsubseteqV(G)$ and $|S|geq2$, an $S$-Steiner tree $T$ is said to be a emph{vertex-rainbow $S$-tree} if the vertices of $V(T)setminusS$ have distinct colors. For a fixed integer $k$ with $2leqkleqn$, the vertex-coloring $c$ of $G$ is called a emph{$k$-vertex-rainbow coloring} if for every $k$-subset $S$ of $V(G)$ there exists a vertex-rainbow $S$-tree. In this case, $G$ is called emph{vertex-rainbow $k$-tree-connected}. The minimum number of colors that are needed in a $k$-vertex-rainbow coloring of $G$ is called the emph{$k$-vertex-rainbow index} of $G$, denoted by $rv{x}_k(G)$. When $k=2$, $rv{x}_2(G)$ is nothing new but the vertex-rainbow connection number $rvc(G)$ of $G$. In this paper, sharp upper and lower bounds of $srv{x}_k(G)$ are given for a connected graph $G$ of order $n$, that is, $0leqsrv{x}_k(G)leqn-2$. We obtain the Nordhaus-Guddum results for $3$-vertex-rainbow index, and show that $rv{x}_3(G)+rv{x}_3(overlineG)=4$ for $n=4$ and $2leqrv{x}_3(G)+rv{x}_3(overlineG)leqn-1$ for $ngeq5$. Let $t(n,k,ell)$ denote the minimal size of a connected graph $G$ of order $n$ with $rv{x}_k(G)leqell$, where $2leqellleqn-2$ and $2leqkleqn$. The upper and lower bounds for $t(n,k,ell)$ are also obtained.

Full work available at URL: https://arxiv.org/abs/1502.00151

Recommendations

• Note on the vertex-rainbow index of a graph
• The rainbow vertex-index of complementary graphs
• The complexity of determining the vertex-rainbow index of graphs
• scientific article; zbMATH DE number 6761154
• Vertex rainbow colorings of graphs
• The 3-rainbow index of a graph
• The vertex-rainbow connection number of some graph operations
• Some results on the 3-vertex-rainbow index of a graph
• Note on the upper bound of the rainbow index of a graph
• The complexity of determining the rainbow vertex-connection of a graph

zbMATH Keywords

connectivityvertex coloringNordhaus-Gaddum typevertex-rainbow \(S\)-treevertex-rainbow index

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Graph theory
• On rainbow connection
• The 3-rainbow index of a graph
• Graphs with 4-rainbow index 3 and \(n-1\)
• The \((k,\ell)\)-rainbow index of random graphs
• Solutions to conjectures on the \((k,\ell)\)-rainbow index of complete graphs
• The rainbow connectivity of a graph
• Rainbow trees in graphs and generalized connectivity
• Rainbow connection in graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• On the rainbow vertex-connection
• Steiner distance in graphs
• On minimally rainbow \(k\)-connected graphs
• A survey of Nordhaus-Gaddum type relations
• On Complementary Graphs
• Nordhaus-Gaddum-type bounds for the rainbow vertex-connection number of a graph
• Steiner tree problems in computer communication networks.
• Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
• Title not available (Why is that?)
• Note on minimally \(d\)-rainbow connected graphs
• Graphs with 3-rainbow index \(n-1\) and \(n-2\)
• The complexity of determining the vertex-rainbow index of graphs

Cited In (9)

• Title not available (Why is that?)
• Some results on the 3-total-rainbow index
• More on the minimum size of graphs with given rainbow index
• Some results on the 3-vertex-rainbow index of a graph
• Note on the vertex-rainbow index of a graph
• Some upper bounds for 3-rainbow index of graphs
• The complexity of determining the vertex-rainbow index of graphs
• Proper connection number of graph products
• A survey on rainbow (vertex-)index of graphs

This page was built for publication: The vertex-rainbow index of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726646)