On a Special Case of the Generalized Neighbourhood Problem
<|reference_start|>On a Special Case of the Generalized Neighbourhood Problem: For a given finite class of finite graphs H, a graph G is called a realization of H if the neighbourhood of its any vertex induces the subgraph isomorphic to a graph of H. We consider the following problem known as the Generalized Neighbourhood Problem (GNP): given a finite class of finite graphs H, does there exist a non-empty graph G that is a realization of H? In fact, there are two modifications of that problem, namely the finite (the existence of a finite realization is required) and infinite one (the realization is required to be infinite). In this paper we show that GNP and its modifications for all finite classes H of finite graphs are reduced to the same problems with an additional restriction on H. Namely, the orders of any two graphs of H are equal and every graph of H has exactly s dominating vertices.<|reference_end|>
@article{naidenko2001on,
    title={On a Special Case of the Generalized Neighbourhood Problem},
    author={V. Naidenko, Yu. Orlovich},
    journal={arXiv preprint arXiv:cs/0111061},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0111061},
    primaryClass={cs.DM}
}