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

NEW

Problem: For a finite simple graph $G$, let $N[v]$ be the closed neighborhood of $v$. A labeling $f:V(G)\to[k]$ is closed distinguishing if for every edge $uv$ with $N[u]\ne N[v]$,

Let $dis[G]$ be the least such $k$. A coloring is strong closed distinguishing if the color-multisets on $N[u]$ and $N[v]$ differ for every such edge $uv$; let $dis_s[G]$ be the least number of colors.

The intended asymptotic statement is: there are constants $c,N>0$ such that for every $n\ge N$, some graph $G$ on exactly $n$ vertices satisfies

The literal phrase “for each positive integer $n$” cannot include a positive $\Omega(\sqrt n)$ lower bound at $n=1$, so this is read in the standard asymptotic sense.

Result: The statement is true. In fact one may take $c=1/8$ for all $n\ge80$.

For $t\ge2$, construct $G_t$ as follows. Let

span a clique. Add independent sets $X=\{x_1,\dots,x_t\}$ and $Y=\{y_1,\dots,y_t\}$. Join $x_a$ to $v_{ij}$ iff $a\le i$, and join $y_b$ to $v_{ij}$ iff $b\le j$. Then $|V(G_t)|=t^2+2t$.

Color $R\cup X$ with color $A$, and $Y$ with color $B$. The multiset on $N[v_{ij}]$ has counts

on $N[x_a]$ it has counts

and on $N[y_b]$ it has counts

These distinguish every adjacent pair with distinct closed neighborhoods: core-core pairs differ by $(i,j)$; core-$X$ pairs differ in the $B$-count; core-$Y$ pairs either differ in $B$-count, or when $j=1$, compare $(t^2+i,1)\ne(t^2,1)$. Hence $dis_s[G_t]\le2$.

Now let $f:V(G_t)\to[k]$ be any closed distinguishing labeling. For core vertices,

where $C=\sum_{z\in R}f(z)$, $P_i=\sum_{a\le i}f(x_a)$, and $Q_j=\sum_{b\le j}f(y_b)$. The $t^2$ core vertices are mutually adjacent and have distinct closed neighborhoods, so the $t^2$ values $P_i+Q_j$ are distinct. But

so there are at most $2tk-1$ possible values. Thus $t^2\le 2tk-1$, giving $k\ge t/2$. Therefore

for $t\ge8$.

For arbitrary $n\ge80$, take

so $t^2+2t\le n$, and add $n-(t^2+2t)$ isolated vertices to $G_t$. Isolated vertices impose no adjacent-neighborhood constraints, so both $dis$ and $dis_s$ are unchanged. Also $t\ge \sqrt n/2$. Hence the resulting $n$-vertex graph $G$ satisfies

Citation: Definitions and the problem are from Dehghan–Mollahajiaghaei, “On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs,” arXiv:1611.03181. The construction above is self-contained.