Graphs whose neighborhoods have no special cycles

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

26 Citaten (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.
Originele taal-2Engels
Pagina's (van-tot)177-182
TijdschriftDiscrete Mathematics
StatusGepubliceerd - 1983
Extern gepubliceerdJa


Duik in de onderzoeksthema's van 'Graphs whose neighborhoods have no special cycles'. Samen vormen ze een unieke vingerafdruk.

Citeer dit