Median graphs and Helly subgraphs

H.M. Mulder, A. Schrijver

Research output: Contribution to journalArticleAcademicpeer-review

38 Citations (Scopus)

Abstract

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
Volume25
Issue number1
DOIs
Publication statusPublished - 1979

Fingerprint

Median Graph
Hypergraph
Subgraph
One to one correspondence
Distance Function
Connected graph
Complement
Interval
Graph in graph theory
Vertex of a graph

Cite this

Mulder, H.M. ; Schrijver, A. / Median graphs and Helly subgraphs. In: Discrete Mathematics. 1979 ; Vol. 25, No. 1. pp. 41-50.
@article{0561220bf41e488484addce01b5389ca,
title = "Median graphs and Helly subgraphs",
abstract = "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).",
author = "H.M. Mulder and A. Schrijver",
year = "1979",
doi = "10.1016/0012-365X(79)90151-1",
language = "English",
volume = "25",
pages = "41--50",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "1",

}

Mulder, HM & Schrijver, A 1979, 'Median graphs and Helly subgraphs', Discrete Mathematics, vol. 25, no. 1, pp. 41-50. https://doi.org/10.1016/0012-365X(79)90151-1

Median graphs and Helly subgraphs. / Mulder, H.M.; Schrijver, A.

In: Discrete Mathematics, Vol. 25, No. 1, 1979, p. 41-50.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Median graphs and Helly subgraphs

AU - Mulder, H.M.

AU - Schrijver, A.

PY - 1979

Y1 - 1979

N2 - 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).

AB - 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).

U2 - 10.1016/0012-365X(79)90151-1

DO - 10.1016/0012-365X(79)90151-1

M3 - Article

VL - 25

SP - 41

EP - 50

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1

ER -