Graphs whose neighborhoods have no special cycles

A.E. Brouwer, P. Duchet, A. Schrijver

Research output: Contribution to journalArticleAcademicpeer-review

24 Citations (Scopus)


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 languageEnglish
Pages (from-to)177-182
JournalDiscrete Mathematics
Publication statusPublished - 1983
Externally publishedYes


Dive into the research topics of 'Graphs whose neighborhoods have no special cycles'. Together they form a unique fingerprint.

Cite this