کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651019 1342516 2006 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Building blocks for the variety of absolute retracts
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Building blocks for the variety of absolute retracts
چکیده انگلیسی

Given a graph H with a labelled subgraph G, a retraction of H to G   is a homomorphism r:H→Gr:H→G such that r(x)=xr(x)=x for all vertices x in G. We call G a retract of H. While deciding the existence of a retraction to a fixed graph G is NP-complete in general, necessary and sufficient conditions have been provided for certain classes of graphs in terms of holes, see for example Hell and Rival.For any integer k⩾2k⩾2 we describe a collection of graphs that generate the variety ARkARk of graphs G with the property that G is a retract of H whenever G is a subgraph of H and no hole in G of size at most k is filled by a vertex of H  . We also prove that ARk⊂NUFk+1ARk⊂NUFk+1, where NUFk+1NUFk+1 is the variety of graphs that admit a near unanimity function of arity k+1k+1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 15, 6 August 2006, Pages 1758–1764
نویسندگان
, ,