For a undirected graph $G$, is there a algorithm that found all sets of nodes that satisfies the rule that: in such a set, any pair of nodes have a distance larger than $N$, where $N$ is a positive number larger than 2.
For a short example, if we have a graph like this:
1-2-3 | | | 4-5-6 | | | 7-8-9
which has nine nodes that are denoted by 1-9. The algorithm should then find such sets:[1,3,5,7,9], [2,4,6,8], [1,6,7], [3,4,9]...,[7,2,9],[1,8,3].
My original description is a bit unclear.
The set must be 'greeding' or 'complete', so that any node that is not in that set must at least be the neighbor (distance = 1) of one node in the set.
For a bit about the problem background. I am generating a lattice model for a material. The base structure I used is a bond network containing 46 atoms that each has 4 neighbours (so the degree of each node is 4). I then substitute some atoms (16 in this case) with another type of atoms. Unfortunately, the new atoms do not like to 'stay together' (distance = 1) as the energy increase would be too high in this case. You can see that this is a special case of the asked question.
Currently, i have my problem partly solved by using a greed search algorithm in together with some random search. However, i still do not know what is the maximum number of atoms we can substitute in this case. My computer program show that this number might be 17 but i am not sure if larger number would be possible.