کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652413 | 1632598 | 2009 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the Structure of Contractible Vertex Pairs in Chordal Graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 33, 1 April 2009, Pages 29-36
Journal: Electronic Notes in Discrete Mathematics - Volume 33, 1 April 2009, Pages 29-36