کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649006 1632436 2010 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Independence complexes of chordal graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Independence complexes of chordal graphs
چکیده انگلیسی

We show that the independence complex I(G) of an arbitrary chordal graph GG is either contractible or is homotopy equivalent to the finite wedge of spheres of dimension at least the domination number of GG minus 1. Also it is shown that every finite wedge of spheres (as well as a singleton) is realized as the homotopy type of the independence complex of a chordal graph. A combinatorial consequence is a verification of a conjecture due to Aharoni et al. [2, Conjecture 2.4] for chordal graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issues 15–16, 28 August 2010, Pages 2204–2211
نویسندگان
,