On local properties of finite graphs. (English) Zbl 0531.05056

Sedláček, J.

Graph theory, Proc. Conf., Łagów/Pol. 1981, Lect. Notes Math. 1018, 242-247 (1983).

[For the entire collection see Zbl 0511.00006.]
The author takes as his starting point the following problem of A. Zykov [Problem 30, Theory of graphs and its applications, Proc. Smolenice 1963, 164-165 (1964)]: for which graphs G does there exist a graph H such that the neighborhood of every vertex of H spans a graph isomorphic to G? After a brief survey of the literature on the problem of Zykov, the author discusses three related problems. The first one concerns graphs in which no two vertices have isomorphic neighborhoods; the second one deals with cubic graphs and the numbers of vertices having the same kind of neighborhood; the last problem is similar to the original problem of Zykov, except that the ”neighborhood” of v is formed by all edges (and their endpoins) incident with at least one vertex adjacent to v.

Reviewer: P.Hell

MSC:

05C99

Graph theory

Keywords:

isomorphic neighborhoods; locally connected graphs

Citations:

Zbl 0511.00006