𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Medians of arbitrary graphs

✍ Scribed by Peter J. Slater

Publisher
John Wiley and Sons
Year
1980
Tongue
English
Weight
165 KB
Volume
4
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 for which the subgraph of H induced by the median vertices is isomorphic to G.

πŸ“œ SIMILAR VOLUMES

On Steiner centers and Steiner medians o
On Steiner centers and Steiner medians of graphs
✍ Oellermann, Ortrud R. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 143 KB

Let G be connected graph and S a set of vertices of G. Then a Steiner tree for S is a connected subgraph of G of smallest size (number of edges) that contains S. The size of such a subgraph is called the Steiner distance for S and is denoted by d(S). For a vertex v of G, and integer n, 2 Υ… n Υ… Ν‰V(G)

On compact median graphs
On compact median graphs
✍ Tardif, Claude πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 715 KB

A median graph is called compact if it does not contain an isometric ray. This property is shown to be equivalent to the finite intersection property for convex sets. We show that a compact median graph contains a finite cube that is fixed by all of its automorphisms, and that each family of commuti

n-cubes and median graphs
n-cubes and median graphs
✍ Martyn Mulder πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 156 KB

## Abstract The n‐cube is characterized as a connected regular graph in which for any three vertices __u, v__, and __w__ there is a unique vertex that lies simultaneously on a shortest (__u, v__)‐path, a shortest (__v, w__)‐path, and a shortest (__w, u__)‐path.

Roots of cube polynomials of median grap
Roots of cube polynomials of median graphs
✍ BoΕ‘tjan BreΕ‘ar; Sandi KlavΕΎar; Riste Ε krekovski πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 122 KB

## Abstract The cube polynomial __c__(__G__,__x__) of a graph __G__ is defined as $\sum\nolimits\_{i \ge 0} {\alpha \_i ( G)x^i }$, where Ξ±~i~(__G__) denotes the number of induced __i__‐cubes of __G__, in particular, Ξ±~0~(__G__) = |__V__(__G__)| and Ξ±~1~(__G__) = |__E__(__G__)|. Let __G__ be a medi

Infinite median graphs, (0, 2)-graphs, a
Infinite median graphs, (0, 2)-graphs, and hypercubes
✍ Hans-J. Bandelt; Henry Martyn Mulder πŸ“‚ Article πŸ“… 1983 πŸ› John Wiley and Sons 🌐 English βš– 450 KB

Hypercubes are characterized among connected bipartite graphs by interval conditions in several ways. These results are based on the following two facts: (i) connected bipartite graphs are median provided that all their intervals induce median graphs, and (ii) median (0, 2)graphs are hypercubes. No