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

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