A lower bound and several exact results on the d-lucky number

摘要

If ℓ:V(G)→N is a vertex labeling of a graph G=(V(G),E(G)), then the d-lucky sum of a vertex u ∈ V(G) is dℓ(u)=dG(u)+∑v∈N(u)ℓ(v). The labeling ℓ is a d-lucky labeling if dℓ(u) ≠ dℓ(v) for every uv ∈ E(G). The d-lucky number ηdl(G) of G is the least positive integer k such that G has a d-lucky labeling V(G) → [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 Gm,n-web graphs and graphs obtained by attaching the same number of pendant vertices to the vertices of a generalized cocktail-party graph.