TOPICS
Search

Median Graph


MedianGraph

Call a graph vertex m(a,b,c) a median of a graph G if it lies on all shortest paths between each pair of vertices (a,b), (b,a), and (c,a) in G. A median graph is then defined as a simple graph in which every three vertices possess a unique median.

A connected graph G is a median graph iff it is an induced graph of an hypercube graph such that for any three vertices of G their median in the hypercube graph is also a vertex of G (Mulder 1978, Munarini 2019).

The numbers of median graphs on n=1, 2, ... vertices are 1, 1, 1, 3, 4, 11, 23, 69, 178, 567, ... (OEIS A292623), the first few of which are illustrated above.

The graph Cartesian product of two median graphs is a median graph.

Trees are median graphs, so path and star graphs are as well.

Grid graphs (of all dimensions) are median graphs, so ladder graphs are as well.

Other classes of graphs that are median include book S_(n+1) square P_2, Fibonacci cube, gear (for n>3), hypercube, and stacked book graphs.


See also

Graph Cartesian Product, Tree

Explore with Wolfram|Alpha

References

Imrich, W.; Klavžar, S.; and Mulder, H. M. "Median Graphs and Triangle-Free Graphs." SIAM J. Disc. Math. 12, 111-118, 1999.Mulder, M. "The Structure of Median Graphs." Disc. Math. 24, 197-204, 1978.Munarini, E. "Pell Graphs." Disc. Math. 342, 2415-2428, 2019.

Cite this as:

Weisstein, Eric W. "Median Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MedianGraph.html

Subject classifications