Rainbow vertex k-connection in graphs
Rainbow vertex k-connection in graphs
复制标题
DOI：
10.1016/j.dam.2013.04.025
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Henry Liu;Ângela Mestre;Teresa Sousa
中科院分区：
文献类型：
--
作者：
Henry Liu;Ângela Mestre;Teresa Sousa
设k为正整数，G为k连通图。如果一条边缘有颜色的路径的边缘有不同的颜色，它就是彩虹。G的彩虹k连接数，用rck (G)表示，是为G的边缘上色所需的最小颜色数，以便G的任意两个顶点通过k个内部顶点不相交的彩虹路径连接。函数rck (G)是由Chartrand， Johns， McKeon和Zhang在2009年首次提出的，并引起了人们的极大兴趣。在本文中，我们考虑了函数rck (G)的一个版本，它涉及到顶点着色。顶点颜色的路径是顶点彩虹，如果它的内部顶点有不同的颜色。G的彩虹顶点k-连接数，用r v c k (G)表示，是为G的顶点上色所需的最小颜色数，以便G的任意两个顶点通过k个内部顶点-不相交顶点-彩虹路径连接。我们将研究当G是环、轮和完全多部图时的函数r v c k (G)。我们也构造图G其中rck (G)远大于rvck (G)反之亦然所以我们一般不能用另一个来限定rck (G)和rvck (G)中的一个。
Let k be a positive integer and G be a k-connected graph. An edge-coloured path is rainbow if its edges have distinct colours. The rainbow k-connection number of G, denoted by r c k (G), is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function r c k (G) was first introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted considerable interest. In this paper, we consider a version of the function r c k (G) which involves vertex-colourings. A vertex-coloured path is vertex-rainbow if its internal vertices have distinct colours. The rainbow vertex k-connection number of G, denoted by r v c k (G), is the minimum number of colours required to colour the vertices of G so that any two vertices of G are connected by k internally vertex-disjoint vertex-rainbow paths. We shall study the function r v c k (G) when G is a cycle, a wheel, and a complete multipartite graph. We also construct graphs G where r c k (G) is much larger than r v c k (G) and vice versa so that we cannot in general bound one of r c k (G) and r v c k (G) in terms of the other.