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