✦ LIBER ✦

Generalized eccentricity, radius, and diameter in graphs

✍ Scribed by Dankelmann, Peter; Goddard, Wayne; Henning, Michael A.; Swart, Henda C.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 101 KB
Volume: 34
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199912)34:4<312::aid-net11>3.0.co;2-v

No coin nor oath required. For personal study only.

✦ Synopsis

For a vertex v and a (k Ϫ 1)-element subset P of vertices of a graph, one can define the distance from v to P in various ways, including the minimum, average, and maximum distance from v to P. Associated with each of these distances, one can define the k-eccentricity of the vertex v as the maximum distance over all P and the k-eccentricity of the set P as the maximum distance over all v. If k ϭ 2, one is back with the normal eccentricity. We study here the properties of these eccentricity measures, especially bounds on the associated radius (minimum k-eccentricity) and diameter (maximum k-eccentricity).

📜 SIMILAR VOLUMES

Pebbling in diameter two graphs and prod

Pebbling in diameter two graphs and products of paths

✍ Clarke, T. A.; Hochberg, R. A.; Hurlbert, G. H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

Results regarding the pebbling number of various graphs are presented. We say a graph is of Class 0 if its pebbling number equals the number of its vertices. For diameter d we conjecture that every graph of sufficient connectivity is of Class 0. We verify the conjecture for d = 2 by characterizing t

Extremal graphs of diameter two and give

Extremal graphs of diameter two and given maximum degree, embeddable in a fixed surface

✍ Knor, Martin; ?ir�?, Jozef 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 2 views

It is known that for each d there exists a graph of diameter two and maximum degree d which has at least (d/2) (d + 2)/2 vertices. In contrast with this, we prove that for every surface S there is a constant d S such that each graph of diameter two and maximum degree d ≥ d S , which is embeddable in

A branch-and-cut algorithm for solving g

A branch-and-cut algorithm for solving generalized multiperiod Steiner problems in graphs

✍ Suhl, Uwe H.; Hilbert, Heinrich 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB 👁 2 views

Given is an undirected graph with positive or negative edge weights which represent a profit if an investment such as installing a gas pipe takes place in a given time period. A certain part of the graph may already be piped in previous periods. The task is to extend the piped subgraph in the most p

When a graph is poorer than 100 words: A

When a graph is poorer than 100 words: A comparison of computerised natural language generation, human generated descriptions and graphical displays in neonatal intensive care

✍ Marian van der Meulen; Robert H. Logie; Yvonne Freer; Cindy Sykes; Neil McIntosh 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB

## Abstract Volunteer staff from a Neonatal Intensive Care Unit (NICU) were presented with sets of anonymised physiological data recorded over approximately 45 minute periods from former patients. Staff were asked to select medical/nursing actions appropriate for each of the patients whose data wer