On a Special Case of the Generalized Neighbourhood Problem

Details On a Special Case of the Generalized Neighbourhood Problem On a Special Case of the Generalized Neighbourhood Problem

2001-11-29

arxiv.org/abs/cs/0111061v2

Computer Science

Discrete Mathematics

13 pages, 3 figures, in Russian

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On a Special Case of the Generalized Neighbourhood Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On a Special Case of the Generalized Neighbourhood Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a Special Case of the Generalized Neighbourhood Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-177068