## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  797.05056
Autor:  Clark, Lane; Entringer, Roger C.; Erdös, Paul; Sun, Huicheng; Székely, László
Title:  Extremal problems for the Bondy-Chvátal closure of a graph. (In English)
Source:  Rees, Rolf S. (ed.), Graphs, matrices, and designs. Festschrift in honor of Norman J. Pullman. New York: Marcel Dekker, Inc. Lect. Notes Pure Appl. Math. 139, 73-83 (1993).
Review:  Authors' abstract: Let f(n) denote the maximum diameter of all graphs of order n whose Bondy-Chvátal n-closure is complete. It is shown that 3.2 log n-9 \leq f(n) \leq 8.3 log n+16. Let h(n) denote the maximum ratio of the number of edges in the n-closure of a graph of order n to the number of edges in the graph. It is shown that h(n) < 4; this bound is sharp.
Reviewer:  B.Andrásfai (Budapest)
Classif.:  * 05C35 Extremal problems (graph theory)
Keywords:  extremal problems; Bondy-Chvátal closure; maximum diameter; bound

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag