A new characterization of median graphs (Q1322201)

From MaRDI portal





scientific article; zbMATH DE number 562607
Language Label Description Also known as
default for all languages
No label defined
    English
    A new characterization of median graphs
    scientific article; zbMATH DE number 562607

      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

      Identifiers