کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648923 | 1632446 | 2007 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Triangulated neighborhoods in even-hole-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
An even-hole-free graph is a graph that does not contain, as an induced subgraph, a chordless cycle of even length. A graph is triangulated if it does not contain any chordless cycle of length greater than three, as an induced subgraph. We prove that every even-hole-free graph has a node whose neighborhood is triangulated. This implies that in an even-hole-free graph, with n nodes and m edges, there are at most n+2mn+2m maximal cliques. It also yields an O(n2m)O(n2m) algorithm that generates all maximal cliques of an even-hole-free graph. In fact these results are obtained for a larger class of graphs that contains even-hole-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 9–10, 6 May 2007, Pages 1065–1073
Journal: Discrete Mathematics - Volume 307, Issues 9–10, 6 May 2007, Pages 1065–1073
نویسندگان
Murilo V.G. da Silva, Kristina Vušković,