A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-complete to decide whether a given star system is graphical.
What is the minimum occurrence of each element such that the problem remains $NP$-complete?
EDIT 12-12-2010: I added another question:
What is the most restricted class of graphs for which the problem remains $NP$-complete?
For instance, Is the star system problem $NP$-complete if the target graph is cubic? If not, What is the minimum $k$ such that the problem remains $NP$-complete for $k$-regular target graphs?