On graphs with given neighbourhoods. (English) Zbl 0674.05061

Bugata, Peter; Horňák, Mirko; Jendrol, Stanislav

Čas. Pěstování Mat. 114, No. 2, 146-154 (1989).

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

MSC:

05C99

Graph theory

Keywords:

realizability of graphs; k-neighbourhood; closed k-neighbourhood