کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419945 683877 2013 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Rainbow vertex kk-connection in graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Rainbow vertex kk-connection in graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 16–17, November 2013, Pages 2549–2555
نویسندگان
, , ,