Trahtenbrot-Zykov problem and NP-completeness (Q1201257)

The Trahtenbrot-Zykov problem for a class \({\mathcal L}\) of graphs is the following: Given a finite graph \(H \in{\mathcal L}\) does there exist a (possibly infinite) graph \(G\) in which the neighbours of any vertex induce a graph isomorphic to \(H\)? For many simple families \({\mathcal L}\), such as paths, cycles, subdivided stars, or star forests, it is known precisely which graphs \(H\) admit such a \(G\). The problem is known to be undecidable when \({\mathcal L}\) is the class of all graphs, but decidable when \({\mathcal L}\) is the class of all trees. The author constructs a class \({\mathcal L}\) of graphs for which the problem is NP-complete. This is done by a clever construction which transforms the hamiltonian cycle problem in triangle-free cubic graphs to the Trahtenbrot-Zykov problem for a suitable family \({\mathcal L}\).