On graphs with given neighbourhoods. (English) Zbl 0674.05061

Let k be a positive integer. The k-neighbourhood (or closed k- neighbourhood) of a vertex v in an undirected graph G is the subgraph of G induced by the set of all vertices of G whose distance from v is equal (or less than or equal, respectively) to k. The closed k-neighbourhood is also called the k-neighbourhood. A graph H is said to be k-realizable (or k-realizable), if there exists a graph G in which the k-neighbourhood (or k-neighbourhood respectively) of every vertex of G is isomorphic to H. The paper shows a relationship between 1-realizability and 2- realizability of graphs, presents some necessary and some sufficient conditions for k-realizability and solves the Zykov problem of 1- realizability for two classes of graphs.
Reviewer: B.Zelinka


05C99 Graph theory