A new characterization of median graphs (Q1322201)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new characterization of median graphs |
scientific article |
Statements
A new characterization of median graphs (English)
0 references
10 October 1994
0 references
Given two vertices \(u\) and \(v\) of a graph, the interval \(l(u,v)\) is the set of vertices lying on some shortest path from \(u\) to \(v\). A graph is a median graph, if for any three vertices \(u\), \(v\) and \(w\), the intersection of the intervals \(l(u,v)\), \(l(u,w)\) and \(l(v,w)\) is a one- element set. A graph is Hilbertian if for any three vertices \(u\), \(v\) and \(w\), the interval \(l(u,v)\) contains the unique nearest vertex from \(w\). The author shows that a graph is median if and only if it is Hilbertian.
0 references
distances
0 references
Hilbertian graphs
0 references
shortest path
0 references
median graph
0 references