کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875474 | 1441957 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Leaf realization problem, caterpillar graphs and prefix normal words
ترجمه فارسی عنوان
مشکل تحقق برگ، نمودارهای کپیرایت و پیشوند کلمات طبیعی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نظریه گراف، ترکیبیات بر روی کلمات، زیرزمین منجر شده، برگ، پیشوند واژه های عادی، پیشوند فرم طبیعی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a simple graph G with n vertices and a natural number iâ¤n, let LG(i) be the maximum number of leaves that can be realized by an induced subtree T of G with i vertices. We introduce a problem that we call the leaf realization problem, which consists in deciding whether, for a given sequence of n+1 natural numbers (â0,â1,â¦,ân), there exists a simple graph G with n vertices such that âi=LG(i) for i=0,1,â¦,n. We present basic observations on the structure of these sequences for general graphs and trees. In the particular case where G is a caterpillar graph, we exhibit a bijection between the set of the discrete derivatives of the form (ÎLG(i))1â¤iâ¤nâ3 and the set of prefix normal words.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 732, 7 July 2018, Pages 1-13
Journal: Theoretical Computer Science - Volume 732, 7 July 2018, Pages 1-13
نویسندگان
Alexandre Blondin Massé, Julien de Carufel, Alain Goupil, Mélodie Lapointe, Ãmile Nadeau, Ãlise Vandomme,