A new characterization of median graphs

DOI10.1016/0012-365X(94)90128-7MaRDI QIDQ1322201zbMATH OpenFDO

Authors Abdelhafid Berrachedi

Publication date 10 October 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)90128-7

zbMATH Keywords

distancesHilbertian graphsmedian graphshortest path

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

• A characterization of median graphs
• Characterizing almost-median graphs
• Median graphs and hypercubes, some new characterizations
• scientific article; zbMATH DE number 1339499
• A charaterization of planar median graphs
• Characterizing almost-median graphs. II.
• scientific article; zbMATH DE number 2043370
• Generalized median graphs and applications
• On graphs containing a given graphs as median

Cites work

• scientific article; zbMATH DE number 3697163 (Why is no real title available?)
• Median algebras
• Median graphs and Helly hypergraphs
• Medians in median graphs

Cited in

(16)

• The median function on graphs with bounded profiles
• A fixed cube theorem for median graphs
• Pseudo-median graphs: Decomposition via amalgamation and Cartesian multiplication
• Recognizing median graphs in subquadratic time
• On median graphs and median grid graphs
• Generalized Hamming graphs: some new results
• Almost self-centered median and chordal graphs
• Two relations for median graphs
• Two-ended regular median graphs
• Daisy cubes and distance cube polynomial
• scientific article; zbMATH DE number 3851138 (Why is no real title available?)
• Vertex-transitive median graphs of non-exponential growth
• Multimedian graphs and their properties
• On all-path convex, gated and Chebyshev sets in graphs
• A characterization of median graphs
• Axiomatic characterization of the median function of a block graph

This page was built for publication: A new characterization of median graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322201)