کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419945 | 683877 | 2013 | 7 صفحه PDF | دانلود رایگان |

Let kk be a positive integer and GG be a kk-connected graph. An edge-coloured path is rainbow if its edges have distinct colours. The rainbow kk-connection number of GG, denoted by rck(G)rck(G), is the minimum number of colours required to colour the edges of GG so that any two vertices of GG are connected by kk internally vertex-disjoint rainbow paths. The function rck(G)rck(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 rck(G)rck(G) which involves vertex-colourings. A vertex-coloured path is vertex-rainbow if its internal vertices have distinct colours. The rainbow vertex kk-connection number of GG, denoted by rvck(G)rvck(G), is the minimum number of colours required to colour the vertices of GG so that any two vertices of GG are connected by kk internally vertex-disjoint vertex-rainbow paths. We shall study the function rvck(G)rvck(G) when GG is a cycle, a wheel, and a complete multipartite graph. We also construct graphs GG where rck(G)rck(G) is much larger than rvck(G)rvck(G) and vice versa so that we cannot in general bound one of rck(G)rck(G) and rvck(G)rvck(G) in terms of the other.
Journal: Discrete Applied Mathematics - Volume 161, Issues 16–17, November 2013, Pages 2549–2555