Rainbow connection in graphs
Rainbow connection in graphs
复制标题
DOI：
10.21136/mb.2008.133947
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
G. Chartrand;Garry L. Johns;K. A. McKeon;Ping Zhang
中科院分区：
文献类型：
--
作者：
G. Chartrand;Garry L. Johns;K. A. McKeon;Ping Zhang
设$G$是一个非平凡连通图，其上定义了一个着色$c\：e(G)\right tarrow\ldots，k\r括号$，$k\in{\mathbb{N}}$，其中相邻边可以着色相同。如果$P$的两条边没有相同的颜色，则$G$中的路径$P$是彩虹路径。如果$G$的每两个顶点$u$和$v$都有一条彩虹$u-v$路，则图$G$是彩虹连通的。存在这样的$k$边着色的最小$k$是$G$的彩虹连通数$\mathop{\mathm Rc}(G)$。如果对于每一对不同的顶点$u，v$，$G$包含一条彩虹$u-v$测地线，则$G$是强彩虹连通的。存在强彩虹连通图的$k$边着色的最小$k$称为强彩虹连通数$\mathop{\mathm src}(G)$of$G$.这样，对每个非平凡连通图$G$，都有$\mathop{\mathm Rc}(G)\le\mathop{\mathm src}(G)$。对于所有完全多部图$G$以及其他图类，都确定了$\mathop{\mathm Rc}(G)$和$\mathop{\mathm src}(G)$。对每一对$a，b$且$a3$和$bge(5a-6)/3$的整数，证明了存在一个连通图$G$，使得$\mathop{\mathm rc}(G)=a$和$\mathop{\mathm src}(G)=b$.
Let $G$ be a nontrivial connected graph on which is defined a coloring $c\: E(G) \rightarrow \lbrace 1, 2, \ldots , k\rbrace $, $k \in {\mathbb{N}}$, of the edges of $G$, where adjacent edges may be colored the same. A path $P$ in $G$ is a rainbow path if no two edges of $P$ are colored the same. The graph $G$ is rainbow-connected if $G$ contains a rainbow $u-v$ path for every two vertices $u$ and $v$ of $G$. The minimum $k$ for which there exists such a $k$-edge coloring is the rainbow connection number $\mathop {\mathrm rc}(G)$ of $G$. If for every pair $u, v$ of distinct vertices, $G$ contains a rainbow $u-v$ geodesic, then $G$ is strongly rainbow-connected. The minimum $k$ for which there exists a $k$-edge coloring of $G$ that results in a strongly rainbow-connected graph is called the strong rainbow connection number $\mathop {\mathrm src}(G)$ of $G$. Thus $\mathop {\mathrm rc}(G) \le \mathop {\mathrm src}(G)$ for every nontrivial connected graph $G$. Both $\mathop {\mathrm rc}(G)$ and $\mathop {\mathrm src}(G)$ are determined for all complete multipartite graphs $G$ as well as other classes of graphs. For every pair $a, b$ of integers with $a \ge 3$ and $b \ge (5a-6)/3$, it is shown that there exists a connected graph $G$ such that $\mathop {\mathrm rc}(G)=a$ and $\mathop {\mathrm src}(G)=b$.