Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0536.05057
Bandelt, H.J.; Barthélemy, J.P.
Medians in median graphs. (English)
[J] Discrete Appl. Math. 8, 131-142 (1984). ISSN 0166-218X

If G is an undirected graph, V(G) is its vertex set and $A\subseteq V(G)$, then a median of A is any vertex of G which has the minimal sum of distance from all vertices of A. If each subset of V(G) having three vertices has exactly one median, then G is called a median graph. The properties of median graphs are studied. The interrelation between median graphs and median semilattices is shown; a median semilattice is a meet semilattice $(X,\le)$ such that every principle ideal $\{$ $x\vert x\le a\}$ is a distributive lattice and any three elements have an upper bound whenever each pair of them does. At the end of the paper the concept of a local median is introduced and interrelations between medians and Condorcet vertices are described.
[B.Zelinka]

MSC 2000:: *05C99 Graph theory
05C38 Paths and cycles
06A12 Semilattices

Keywords: local median; Condorcet vertex; median semilattices

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]