کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647030 | 1342322 | 2015 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Length lower bounds for reflecting sequences and universal traversal sequences
ترجمه فارسی عنوان
مرزهای طول پایین برای بازتاب توالی ها و توالی های حرکتی جهانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چرخش نمودار، توالی تراکم جهانی، توالی بازتابی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A universal traversal sequence for the family of all connected d-regular graphs of order n with an edge-labeling is a sequence of {0,1,â¦,dâ1}â that traverses every graph of the family starting at every vertex of the graph. Reflecting sequences are variants of universal traversal sequences. A t-reflecting sequence for the family of all labeled chains of length n is a sequence of {0,1}â that alternately visits the end-vertices and reflects at least t times in every labeled chain of the family. We present an algorithm for finding lower bounds on the lengths of reflecting sequences for labeled chains. Using the algorithm, we show a length lower bound of 19tâ214 for t-reflecting sequences for labeled chains of length 7, which yields the length lower bounds of Ω(n1.51) and Ω(d0.49n2.51) for universal traversal sequences for 2- and d-regular graphs, respectively, of n vertices, where 3â¤dâ¤n17+1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 6, 6 June 2015, Pages 1042-1065
Journal: Discrete Mathematics - Volume 338, Issue 6, 6 June 2015, Pages 1042-1065
نویسندگان
H.K. Dai,