کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419115 681743 2007 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The multiple originator broadcasting problem in graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The multiple originator broadcasting problem in graphs
چکیده انگلیسی

Given a graph GG and a vertex subset SS of V(G)V(G), the broadcasting time with respect to  SS, denoted by b(G,S)b(G,S), is the minimum broadcasting time when using SS as the broadcasting set. And the kk-broadcasting number  , denoted by bk(G)bk(G), is defined by bk(G)=min{b(G,S)|S⊆V(G),|S|=k}bk(G)=min{b(G,S)|S⊆V(G),|S|=k}.Given a graph GG and two vertex subsets SS, S′S′ of V(G)V(G), define d(v,S)=minu∈Sd(v,u), d(S,S′)=min{d(u,v)|u∈Sd(S,S′)=min{d(u,v)|u∈S, v∈S′}v∈S′}, and d(G,S)=maxv∈V(G)d(v,S) for all v∈V(G)v∈V(G). For all kk, 1⩽k⩽|V(G)|1⩽k⩽|V(G)|, the kk-radius   of GG, denoted by rk(G)rk(G), is defined as rk(G)=min{d(G,S)|S⊆V(G)rk(G)=min{d(G,S)|S⊆V(G), |S|=k}|S|=k}.In this paper, we study the relation between the kk-radius and the kk-broadcasting numbers of graphs. We also give the 22-radius and the 22-broadcasting numbers of the grid graphs, and the kk-broadcasting numbers of the complete nn-partite graphs and the hypercubes.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 10, 15 May 2007, Pages 1188–1199
نویسندگان
, , ,