کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949823 | 1440205 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
ترجمه فارسی عنوان
در پیچیدگی الگوریتمی از رأس مجاور بسته تعداد رنگ اختلاف رنگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An assignment of numbers to the vertices of graph G is closed distinguishing if for any two adjacent vertices v and u the sum of labels of the vertices in the closed neighborhood of the vertex v differs from the sum of labels of the vertices in the closed neighborhood of the vertex u unless they have the same closed neighborhood (i.e. N[u]=N[v]). The closed distinguishing number of a graph G, denoted by dis[G], is the smallest integer k such that there is a closed distinguishing labeling for G using integers from the set {1,2,â¦,k}. Also, for each vertex vâV(G), let L(v) denote a list of natural numbers available at v. A list closed distinguishing labeling is a closed distinguishing labeling f such that f(v)âL(v) for each vâV(G). A graph G is said to be closed distinguishing k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list closed distinguishing labeling of G. The closed distinguishing choice number of G, disâ[G], is the minimum natural number k such that G is closed distinguishing k-choosable. In this work we show that for each integer t there is a bipartite graph G such that dis[G]>t. This is an answer to a question raised by Axenovich et al. in (Axenovich et al., 2016) that how ”dis” function depends on the chromatic number of a graph. It was shown that for every graph G with Îâ¥2, dis[G]â¤disâ[G]â¤Î2âÎ+1 and also there are infinitely many values of Î for which G might be chosen so that dis[G]=Î2âÎ+1 (Axenovich et al., 2016). In this work, we prove that the difference between dis[G] and disâ[G] can be arbitrary large and show that for every positive integer t there is a graph G such that disâ[G]âdis[G]â¥t. Also, we improve the current upper bound and give some number of upper bounds for the closed distinguishing choice number by using the Combinatorial Nullstellensatz. Among other results, we show that it is NP-complete to decide for a given planar subcubic graph G, whether dis[G]=2. Also, we prove that for every kâ¥3, it is NP-complete to decide whether dis[G]=k for a given graph G.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 218, 19 February 2017, Pages 82-97
Journal: Discrete Applied Mathematics - Volume 218, 19 February 2017, Pages 82-97
نویسندگان
Ali Dehghan, Mohsen Mollahajiaghaei,