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

Abstract

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 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[k].Also, for each vertex $v\in 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)\in L(v)$ for each $v\in 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, $di{s}_{\ell }[G]$, is the minimum number k such that G is closed distinguishing k-choosable. We show that for each integer t there is a bipartite graph G such that $dis[G]>t$.It was shown that for every graph G with $\Delta \ge 2$, $dis[G]\le di{s}_{\ell }[G]\le {\Delta }^2-\Delta +1$ and there are infinitely values of $\Delta$ for which G might be chosen so that $dis[G]={\Delta }^2-\Delta +1$. We show that the difference between $dis[G]$ and $di{s}_{\ell }[G]$ can be arbitrary large and for every positive integer t there is a graph G such that $di{s}_{\ell }[G]-dis[G]\ge t$. We improve the current upper bound and give some number of upper bounds for the closed distinguishing choice number by using the Combinatorial Nullstellensatz. We show that it is $\mathbf{NP}$-complete to decide for a given planar subcubic graph G, whether dis[G]=2. Also, we prove that for every $k\ge 3$, it is {\bf NP}-complete to decide whether $dis[G]=k$ for a given graph G

To appear in Discrete Applied Mathematics

References in corpus (2)

• The 1-2-3 Conjecture and related problems: a survey
• Algorithmic complexity of proper labeling problems