𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs whose neighborhoods have no special cycles

✍ Scribed by A.E. Brouwer; P. Duchet; A. Schrijver

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
480 KB
Volume
47
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

To a graph G is canonically associated its neighborhood-hypergraph, X(G), formed by the closed neighborhoods of the vertices of G. We characterize the graphs G such that (i) X(G) has no induced cycle, or (ii) #(G) is a balanced hypergraph or (iii) X(G) is triangle free. (i) is another short proof of a result by Farber; (ii) answers a problem asked by C. Berge. The case of strict neighborhoods is also solved.

📜 SIMILAR VOLUMES

A note on graphs whose neighborhoods are
A note on graphs whose neighborhoods aren-cycles
✍ Bruce L. Chilton; Ronald Gould; Albert D. Polimeni 📂 Article 📅 1974 🏛 Springer 🌐 English ⚖ 220 KB

AnSTRACr. Let G be a graph, and let v be a vertex of G. We denote by N(v) the set of vertices of G which are adjacent to v, and by (N(v)) the subgraph of G induced by N(v). We call <N(v)) the neighborhood of v. In a paper of 1968, Agakishieva has, as one of her main theorems, the statement: "Graphs