کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903184 | 1632404 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Helly EPT graphs on bounded degree trees: Characterization and recognition
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The edge-intersection graph of a family of paths on a host tree is called an EPT graph. When the tree has maximum degree h, we say that the graph is [h,2,2]. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly [h,2,2]. In this paper, we present a family of EPT graphs called gates which are forbidden induced subgraphs for [h,2,2] graphs. Using these we characterize by forbidden induced subgraphs the Helly [h,2,2] graphs. As a byproduct we prove that in getting a Helly EPT-representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly [h,2,2] graphs based on their decomposition by maximal clique separators.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 12, December 2017, Pages 2798-2806
Journal: Discrete Mathematics - Volume 340, Issue 12, December 2017, Pages 2798-2806
نویسندگان
L. Alcón, M. Gutierrez, M.P. Mazzoleni,