The structure of median graphs

✍ Scribed by Martyn Mulder

• Publisher: Elsevier Science
• Year: 1978
• Tongue: English
• Weight: 473 KB
• Volume: 24
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(78)90199-1

✦ Synopsis

A median graph is a ewtmected ,~raph, such that for am.' three ,~ertices u, v aad w there is exactly one ~x:rtex x that lies simutt~ neously on a shortest (lz,,) .pa'~5. a shortest (v. w)-path and a shortest (u'.t,~-pa~h. !t is proved that a median graph cm, "t..-obtained from a one-vertex graph by an ¢~pansion procedure. F~om this characterization ~ome nice properties are derived.

O, Introduefioli

D>. [21 the cot!cept of median gt :~ph was introduced. It ~ as shown that there is a ~cs,. ~elation between median graphs and some at first sight fairly distinct mathematical s:ructures. One of tmese is a special class of Heliy hy~er~raphs. This class consists o{ ~he bypergraphs v~ith vertex.-set V and edge-:.~et E c P(V), such that /,, c E ~, V \ A ~ E and E'3A, B~E':ANB=fL in the seque: a structural characterization of median graphs is gNe 1 and some n.~ce ~ropertie:~ are derived.
With s)me minor adaptations the terminology of Bondy and Mmty [1] is adopted.
L Definitious :rod preliml!~aries t.,:t: G =.:(1,~ E) be a simple Icoptess graph with vertex-set V., edge-set .E and distance fut:ctior~ d. The grapL G is a median graph if G is connected, and for an,., three vertices u, v and w of G there is exactly one vertex x, called the median of u. r ~?nd w and denoted by (u. ~:~, w), .~,uch that d (u, xl ÷ d(x, v) = d(u, v) d(r. ,: ,-! ~y~-, v.,)= d(v, w) d(w, a ) 4 d(x, ~) :,. d(w, u).