Graphs with prescribed neighbourhood graphs. (English) Zbl 0579.05045

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


05C75 Structural characterization of families of graphs
Full Text: EuDML


[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.