Abstract
To a graph G is canonically associated its neighborhood-hypergraph, N(G), formed by the closed neighborhoods of the vertices of G. We characterize the graphs G such that (i) N(G) has no induced cycle, or (ii) N(G) is a balanced hypergraph or (iii) N(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.
Original language | English |
---|---|
Pages (from-to) | 177-182 |
Journal | Discrete Mathematics |
Volume | 47 |
DOIs | |
Publication status | Published - 1983 |
Externally published | Yes |