✦ LIBER ✦

The generalized diameter of a graph

✍ Scribed by Chih-Kang Eric Chen; R. S. Garfinkel

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 198 KB
Volume: 12
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230120310

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We generalize the concept of the diameter of a graph G = (N, A) to allow for location of points not on the nodes. It is shown that there exists a finite set of candidate points which determine this generalized diameter. Given the matrix of shortest paths, an o (|A|^2^) algorithm is developed and tested.

📜 SIMILAR VOLUMES

Generalized eccentricity, radius, and di

Generalized eccentricity, radius, and diameter in graphs

✍ Dankelmann, Peter; Goddard, Wayne; Henning, Michael A.; Swart, Henda C. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB 👁 1 views

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 d

Automorphism group and diameter of a gra

Automorphism group and diameter of a graph

✍ P. Dankelmann; D. Erwin; S. Mukwembi; B. G. Rodrigues; E. Mwambene; G. Sabidussi 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB 👁 1 views

## Abstract Given a connected graph Γ of order __n__ and diameter __d__, we establish a tight upper bound for the order of the automorphism group of Γ as a function of __n__ and __d__, and determine the graphs for which the bound is attained. © 2011 Wiley Periodicals, Inc. J Graph Theory.

The Diameter of Sparse Random Graphs

✍ Fan Chung; Linyuan Lu 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 150 KB

We consider the diameter of a random graph G n p for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of rand

On the Spectrum, the Growth, and the Dia

On the Spectrum, the Growth, and the Diameter of a Graph

✍ N. Hajaj 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 171 KB

A lower bound is given for the harmonic mean of the growth in a finite undirected graph 1 in terms of the eigenvalues of the Laplacian of 1. For a connected graph, this bound is tight if and only if the graph is distance-regular. Bounds on the diameter of a ``sphere-regular'' graph follow. Finally,

Diameters of iterated clique graphs of c

Diameters of iterated clique graphs of chordal graphs

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

A family of graphs and the degree/diamet

A family of graphs and the degree/diameter problem

✍ Geoffrey Exoo 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 1 views

## Abstract We investigate a family of graphs relevant to the problem of finding large regular graphs with specified degree and diameter. Our family contains the largest known graphs for degree/diameter pairs (3, 7), (3, 8), (4, 4), (5, 3), (5, 5), (6, 3), (6, 4), (7, 3), (14, 3), and (16, 2). We a