标题： 顶点彩虹指数 显示英文标题

标题： The vertex-rainbow index of a graph

摘要： The $k$-rainbow index $rx_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 $rvx_k(G)$ in this paper. 对于图$G=(V,E)$和至少包含两个顶点的集合$S\subseteq V$，\emph{一个$S$-Steiner 树}或\emph{一个连接$S$的史特ainer树}（或简称为\emph{一个$S$-树}）是图$G$的一个子图$T=(V',E')$，该子图是一棵树且具有$S\subseteq V'$。 对于$S\subseteq V(G)$和$|S|\geq 2$，一个$S$-Steiner tree$T$被称为一个\emph{顶点彩虹$S$-树}，如果$V(T)\setminus S$的顶点具有不同的颜色。 对于固定整数$k$且$2\leq k\leq n$，图$G$的顶点着色$c$被称为\emph{$k$-顶点彩虹着色}，如果对于每个$k$子集$S$的$V(G)$，存在一个顶点彩虹$S$-树。 In this case, $G$ is called \emph{顶点彩虹$k$-树连通}. The minimum number of colors that are needed in a $k$-vertex-rainbow coloring of $G$ is called the \emph{$k$-顶点-Rainbow指数} of $G$, denoted by $rvx_k(G)$. 当 $k=2$， $rvx_2(G)$除了是顶点彩虹连通数 $rvc(G)$之外没有新内容 $G$。 在本文中，给出了连通图 $G$ 的阶数为 $n$ 时，$srvx_k(G)$ 的精确上界和下界，即 $0\leq srvx_k(G)\leq n-2$。 我们得到关于$3$-顶点彩虹指数的Nordhaus-Guddum结果，并证明$rvx_3(G)+rvx_3(\overline{G})=4$对$n=4$和$2\leq rvx_3(G)+rvx_3(\overline{G})\leq n-1$对$n\geq 5$。 设$t(n,k,\ell)$表示连通图$G$的阶数为$n$且具有$rvx_k(G)\leq \ell$的最小大小，其中$2\leq \ell\leq n-2$和$2\leq k\leq n$。也得到了$t(n,k,\ell)$的上下界。 显示英文摘要

摘要： The $k$-rainbow index $rx_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 $rvx_k(G)$ in this paper. For a graph $G=(V,E)$ and a set $S\subseteq V$ 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',E')$ of $G$ that is a tree with $S\subseteq V'$. For $S\subseteq V(G)$ and $|S|\geq 2$, an $S$-Steiner tree $T$ is said to be a \emph{vertex-rainbow $S$-tree} if the vertices of $V(T)\setminus S$ have distinct colors. For a fixed integer $k$ with $2\leq k\leq n$, 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 $rvx_k(G)$. When $k=2$, $rvx_2(G)$ is nothing new but the vertex-rainbow connection number $rvc(G)$ of $G$. In this paper, sharp upper and lower bounds of $srvx_k(G)$ are given for a connected graph $G$ of order $n$,\ that is, $0\leq srvx_k(G)\leq n-2$. We obtain the Nordhaus-Guddum results for $3$-vertex-rainbow index, and show that $rvx_3(G)+rvx_3(\overline{G})=4$ for $n=4$ and $2\leq rvx_3(G)+rvx_3(\overline{G})\leq n-1$ for $n\geq 5$. Let $t(n,k,\ell)$ denote the minimal size of a connected graph $G$ of order $n$ with $rvx_k(G)\leq \ell$, where $2\leq \ell\leq n-2$ and $2\leq k\leq n$. The upper and lower bounds for $t(n,k,\ell)$ are also obtained.