✦ LIBER ✦

On graphs with prescribed median I

✍ Scribed by G. R. T. Hendry

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 202 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090407

No coin nor oath required. For personal study only.

✦ Synopsis

The distance of a vertex u in a connected graph H is the sum of all the distances from u to the other vertices of H. The median M(H) of H is the subgraph of H induced by the vertices of minimum distance. For any graph G, let f ( G ) denote the minimum order of a connected graph H satisfying M(H) = G. It is shown that if G has n vertices and minimum degree 6 then f(G) s 2n -6 + 1. Graphs having both median and center prescribed are constructed. It is also shown that if the vertices of a K, are removed from a graph H, then at most r components of the resulting graph contain median vertices of H.

📜 SIMILAR VOLUMES

On vertex critical graphs with prescribe

On vertex critical graphs with prescribed diameter

✍ L. Caccetta; S. EL-Batanouny; J. Huang 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 1 views

## Abstract Let __G__ be connected simple graph with diameter __d__(__G__). __G__ is said __v__^+^‐critical if __d__(__G__−__v__) is greater than __d__(__G__) for every vertex __v__ of __G__. Let D′ = max {__d__(__G__−__v__) : __v__ ∈ __V__(__G__)}. Boals et al. [Congressus Numerantium 72 (1990), 1

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

Regular graphs with prescribed chromatic

Regular graphs with prescribed chromatic number

✍ L. Caccetta; N. J. Pullman 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB

## Abstract We determine the minimum number of edges in a regular connected graph on __n__ vertices, containing a complete subgraph of order __k__ ≤ __n__/2. This enables us to confirm and strengthen a conjecture of P. Erdös on the existence of regular graphs with prescribed chromatic number.

Graphs with prescribed connectivity and

Graphs with prescribed connectivity and line graph connectivity

✍ Douglas Bauer; Ralph Tindell 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract Chartrand and Stewart have shown that the line graph of an __n__‐connected graph is itself __n__‐connected. This paper shows that for every pair of integers __m__ > __n__ > 1 there is a graph of point connectivity __n__ whose line graph has point connectivity __m__. The corresponding qu

Locating median paths on connected outer

Locating median paths on connected outerplanar graphs

✍ Isabella Lari; Federica Ricca; Andrea Scozzari; Ronald I. Becker 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 215 KB 👁 1 views

Existence of graphs with prescribed mean

Existence of graphs with prescribed mean distance

✍ G. R. T. Hendry 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB 👁 1 views