کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949675 | 1440198 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sequences of radius k for complete bipartite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A k-radius sequence for a graph G is a sequence of vertices of G (typically with repetitions) such that for every edge uv of G vertices u and v appear at least once within distance k in the sequence. The length of a shortest k-radius sequence for G is denoted by fk(G). We give an asymptotically tight estimation on fk(G) for complete bipartite graphs which matches a lower bound, valid for all bipartite graphs. We also show that determining fk(G) for an arbitrary graph G is NP-hard for every constant k>1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 225, 10 July 2017, Pages 51-63
Journal: Discrete Applied Mathematics - Volume 225, 10 July 2017, Pages 51-63
نویسندگان
MichaÅ DÄbski, Zbigniew Lonc, PaweÅ RzÄ
żewski,