Another example is the efficient dominating set problem also known as 1-perfect code in graphs. The problem is to determine the existence of a dominating set $C$ in undirected graph such that the shortest path between any two nodes in the dominating set $C$ is at least 3 (edges). The problem was proven to be $NP$-complete independently by many researchers. The problem remains $NP$-complete even for cubic planar graphs. 

D. W. Bange, A. E. Barkauskas, and P. J. Slater. [Efficient dominating sets in graphs][1]. Applications of discrete mathematics, Proc. 3rd SIAM Conf., Clemson/South Carolina 1986, 189-199 (1988)., 1988.

[1]: http://books.google.com.sa/books?id=zgHVZdBAezYC&pg=PA189&lpg=PA189&dq=efficient+dominating+sets+in+graphs+bange&source=bl&ots=IU4uL9pxUN&sig=woTBH0AMz2i2X1f4lDAxLh355hU&hl=en&sa=X&ei=h4SLUsaIBqG57AaljoDYDg&safe=on&redir_esc=y#v=onepage&q=efficient%20dominating%20sets%20in%20graphs%20bange&f=false