| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428587 | Information Processing Letters | 2012 | 4 Pages |
A lucky labeling of a graph G is a function ℓ:V(G)→Nℓ:V(G)→N, such that for every two adjacent vertices v and u of G , ∑w∼vℓ(w)≠∑w∼uℓ(w)∑w∼vℓ(w)≠∑w∼uℓ(w) (x∼yx∼y means that x is joined to y). A lucky number of G , denoted by η(G)η(G), is the minimum number k such that G has a lucky labeling ℓ:V(G)→{1,…,k}ℓ:V(G)→{1,…,k}. We prove that for a given planar 3-colorable graph G determining whether η(G)=2η(G)=2 is NP-complete. Also for every k⩾2k⩾2, it is NP-complete to decide whether η(G)=kη(G)=k for a given graph G.
► We study the computational complexity of lucky number problems. ► We prove that, it is NP-complete to decide for a given planar 3-colorable graph G , whether η(G)=2η(G)=2. ► We reduced 3-Colorability to problem LkLk for k⩾2k⩾2, in polynomial time. ► We concluded for every k⩾2k⩾2, it is NP-complete to decide whether η(G)=kη(G)=k for a given graph G.
