Diameters of graphs: Old problems and new results. (English) Zbl 0695.05029

Chung, Fan R. K.

Combinatorics, graph theory, and computing, Proc. 18th Southeast. Conf., Boca Raton/Fl. 1987, Congr. Numerantium 60, 295-317 (1987).

[For the entire collection see Zbl 0638.00009.]
The diameter D(G) of a connected graph G is the greatest distance between any two vertices of G. In this interesting expository paper, the author reviews a number of problems dealing with diameters. Recent progress is described and many new problems are mentioned. Some potential applications are described as well.
Among the problems discussed are two attributed to B. Elspas [Topological constraints on interconnection limited logic, Switching Circuit Theory and Logical Design 5, 133-147 (1964)]: For positive integers k and D, construct graphs of large order with maximum degree k and diameter D. For positive integers n and k, construct a graph of minimum diameter having order n and maximum degree k. The following problem is due to K. Vijayan and U. S. R. Murty [Sankhyā, Ser. A 26, 299-302 (1964; Zbl 0134.433)]. For positive integers n, D, \(D'\) and s, what is the minimum size of a graph of order n having diameter D with the property that upon the removal of s edges, the diameter of the resulting graph is at most \(D'?\) The author describes a related problem with degree constraints. For positive integers n, D, \(D'\), k and s, what is the minimum size of graph of order n having maximum degree k and diameter D and satisfying the property that upon the removal of s edges, the diameter of the resulting graph is at most \(D'?\) The following two problems on edge additions are also discussed. For a given graph, determine the optimal way to add t edges so that the resulting graph has minimum diameter. For a given graph, add t independent edges to reduce the diameter by as much as possible.
The author also discusses the complexity of several algorithms involving diameter. She concludes by mentioning some variations and generalizations of diameter problems.

Reviewer: G.Chartrand

MSC:

05C38	Paths and cycles
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
05-04	Software, source code, etc. for problems pertaining to combinatorics

Keywords:

diameter of a graph; problems; algorithms

Citations:

Zbl 0638.00009; Zbl 0134.433