کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434224 689704 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reconfiguration of list L(2,1)L(2,1)-labelings in a graph
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Reconfiguration of list L(2,1)L(2,1)-labelings in a graph
چکیده انگلیسی

For an integer k≥0k≥0, suppose that each vertex v of a graph G   has a set C(v)⊆{0,1,…,k}C(v)⊆{0,1,…,k} of labels, called a list of v  . A list L(2,1)L(2,1)-labeling of G   is an assignment of a label in C(v)C(v) to each vertex v of G   such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L(2,1)L(2,1)-labeling of a graph into another list L(2,1)L(2,1)-labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L(2,1)L(2,1)-labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and k≥6k≥6. In contrast, we then show that the problem can be solved in linear time for general graphs if k≤4k≤4. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L(2,1)L(2,1)-labelings of a tree can be transformed into each other.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 544, 7 August 2014, Pages 84–97
نویسندگان
, , , ,