کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10328499 684038 2005 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Strong branchwidth and local transversals
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Strong branchwidth and local transversals
چکیده انگلیسی
We consider representations of chordal graphs as edge intersection graphs of subtrees in a tree of maximum vertex degree 3. A new graph invariant related to the concept of branchwidth is introduced, and a structural characterization theorem is given for the existence of representations where each edge is contained in fewer subtrees than the clique number of the graph represented. As a consequence, a sufficient condition is obtained for chordal graphs to have smaller branchwidth than clique number.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 145, Issue 2, 15 January 2005, Pages 291-296
نویسندگان
,