On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs

详细信息    查看全文

• 作者：Ali Dehghan^a ; ^{alidehghan@sce.carleton.ca} ; Mohsen Mollahajiaghaei^b ; ^{mmollaha@uwo.ca}
• 关键词：Closed distinguishing labeling ; List closed distinguishing labeling ; Strong closed distinguishing labeling ; Computational complexity ; Combinatorial Nullstellensatz
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：19 February 2017
• 年：2017
• 卷：218
• 期：Complete
• 页码：82-97
• 全文大小：483 K
• 卷排序：218

文摘

An assignment of numbers to the vertices of graph GG is closed distinguishing   if for any two adjacent vertices vv and uu the sum of labels of the vertices in the closed neighborhood of the vertex vv differs from the sum of labels of the vertices in the closed neighborhood of the vertex uu unless they have the same closed neighborhood (i.e. N[u]=N[v]N[u]=N[v]). The closed distinguishing number   of a graph GG, denoted by dis[G]dis[G], is the smallest integer kk such that there is a closed distinguishing labeling for GG using integers from the set {1,2,…,k}{1,2,…,k}. Also, for each vertex v∈V(G)v∈V(G), let L(v)L(v) denote a list of natural numbers available at vv. A list closed distinguishing labeling   is a closed distinguishing labeling ff such that f(v)∈L(v)f(v)∈L(v) for each v∈V(G)v∈V(G). A graph GG is said to be closed distinguishing k-choosable   if every kk-list assignment of natural numbers to the vertices of GG permits a list closed distinguishing labeling of GG. The closed distinguishing choice number of GG, disℓ[G]disℓ[G], is the minimum natural number kk such that GG is closed distinguishing kk-choosable. In this work we show that for each integer tt there is a bipartite graph GG such that dis[G]>tdis[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 GG with Δ≥2Δ≥2, dis[G]≤disℓ[G]≤Δ2−Δ+1dis[G]≤disℓ[G]≤Δ2−Δ+1 and also there are infinitely many values of ΔΔ for which GG might be chosen so that dis[G]=Δ2−Δ+1dis[G]=Δ2−Δ+1 (Axenovich et al., 2016). In this work, we prove that the difference between dis[G]dis[G] and disℓ[G]disℓ[G] can be arbitrary large and show that for every positive integer tt there is a graph GG such that disℓ[G]−dis[G]≥tdisℓ[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 GG, whether dis[G]=2dis[G]=2. Also, we prove that for every k≥3k≥3, it is NP-complete to decide whether dis[G]=kdis[G]=k for a given graph GG.