A Lower Bound and Several Exact Results on the $d$-Lucky Number

Abstract

If $\ell :V(G)\to \mathbb{N}$ is a vertex labeling of a graph $G=(V(G),E(G))$, then the $d$-lucky sum of a vertex $u\in V(G)$ is $d_{\ell }(u)=d_G(u)+{\sum }_{v\in N(u)}\ell (v)$. The labeling $\ell$ is a $d$-lucky labeling if $d_{\ell }(u)\ne d_{\ell }(v)$ for every $uv\in E(G)$. The $d$-lucky number ${\eta }_{dl}(G)$ of $G$ is the least positive integer $k$ such that $G$ has a $d$-lucky labeling $V(G)\to [k]$. A general lower bound on the $d$-lucky number of a graph in terms of its clique number and related degree invariants is proved. The bound is sharp as demonstrated with an infinite family of corona graphs. The $d$-lucky number is also determined for the so-called $G_{n,m}$-web graphs and graphs obtained by attaching the same number of pendant vertices to the vertices of a generalized cocktail-party graph.