Zelinka, Bohdan Graphs with prescribed neighbourhood graphs. (English) Zbl 0579.05045 Math. Slovaca 35, 195-197 (1985). Let u be a vertex in a graph G. Then \(N_ G(u)\) denotes the subgraph of G induced by the vertices adjacent to u in G. The subgraph \(N_ G(u)\) is called the neighborhood graph of u in G (also called the link of u in G). The author investigates those graphs G for which \(N_ G(u)\) is isomorphic to the complement of a path (respectively, cycle) for all vertices u of G. In particular, if G is a graph such that \(N_ G(u)\cong \bar P_ n\) (n\(\geq 4)\) for every u, then \(G\cong C_{n+4}\). Also, there exists a graph G with the property that \(N_ G(u)\cong \bar C_ n\) for every vertex u if and only if \(3\leq n\leq 6\). Reviewer: G.Chartrand Cited in 2 Documents MSC: 05C75 Structural characterization of families of graphs Keywords:complement of a cycle; neighborhood graph; complement of a path × Cite Format Result Cite Review PDF Full Text: EuDML References: [1] Theory of Graph and its Applications. Proc. Symp. Smolenice 1983 by M. Fiedler, Prague 1964. [2] SEDLÁČEK J.: Local properties of graphs. (Czech, English summary.) Časop. pěst. mat. 106, 1981, 290-298. · Zbl 0478.05080 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.