✦ LIBER ✦

A new characterization of median graphs

✍ Scribed by Abdelhafid Berrachedi

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 171 KB
Volume: 128
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90128-7

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is Hilbertian if for any three vertices u, v and w, the interval I(u, u) contains a unique nearest vertex p from w. We show that a graph is median if and only if it is Hilbertian.

📜 SIMILAR VOLUMES

Medians of arbitrary graphs

✍ Peter J. Slater 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB

## Abstract For each vertex __u__ in a connected graph __H__, the __distance__ of __u__ is the sum of the distances from __u__ to each of the vertices __v__ of __H.__ A vertex of minimum distance in __H__ is called a __median__ vertex. It is shown that for any graph __G__ there exists a graph __H__

The structure of median graphs

✍ Martyn Mulder 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 473 KB

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

Conditional centers and medians of a gra

Conditional centers and medians of a graph

✍ Edward Minieka 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 454 KB

Median graphs and Helly hypergraphs

✍ H.M. Mulder; A. Schrijver 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 963 KB

A new characterization of proper interva

A new characterization of proper interval graphs

✍ Zygmunt Jackowski 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 379 KB

One of the first characterizations of interval graphs, given by Lekkerkerker and Boland (1962), uses the concept of an asteroidal triple. In this paper we give a similar characterization on the proper interval graphs using the akin concept of an astral triple.

A fixed cube theorem for median graphs

✍ Hans-Jürgen Bandelt; Marcel van de Vel 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 513 KB

The following result is proven: every edge-preserving self-map of a median graph leaves a cube invariant. This extends a fixed edge theorem for trees and parallels a result on invariant simplices in contractible graphs.