Median graphs and Helly subgraphs

H.M. Mulder, A. Schrijver

Research output: Contribution to journalArticleAcademicpeer-review

47 Citations (Scopus)


One-to-one correspondences are established between the following combinatorial structures: (i) median interval structures (or median segments, introduced by Sholander); (ii) maximaL Helly hypergraphs such that with each edge also its complement is in the hypergraph; and (iii) median graphs (connected graphs such that for any three vertices u, v, w there is exactly one vertex x such that d(u,¿) = d(u,x)+d(x,¿), d(¿,w) = d(¿,x)+d(x,w) and d(w, u) = d(w,x)+ d(x, u), where d is the distance function of the graph).
Original languageEnglish
Pages (from-to)41-50
Number of pages10
JournalDiscrete Mathematics
Issue number1
Publication statusPublished - 1979


Dive into the research topics of 'Median graphs and Helly subgraphs'. Together they form a unique fingerprint.

Cite this