Catalog Home Page

Graphs of maximum diameter

Caccetta, L. and Smyth, W.F. (1992) Graphs of maximum diameter. Discrete Mathematics, 102 (2). pp. 121-141.

Link to Open Access version:
*No subscription required


A simple undirected connected graph with minimum degree K is said to be K-restrained. Thus the class of K-restrained graphs includes all K-connected and K-edge-connected graphs, as well as all connected K-regular graphs. An upper bound on the diameter of three of these four classes of graphs is known: for K-restrained (hence for connected K-regular) and for K-connected. We complete the picture by determining an upper bound on the diameter of a K-edge-connected graph of order n; and show that, with the exception of certain connected K-regular graphs, the upper bound is attained by some graph in every class. For K-restrained graphs of order n known to contain a vertex of eccentricity d, a maximum edge-count ϵ(n, d, K) is specified and shown to be a monotone decreasingfunction of d; this result is then used to determine the maximum diameter of a K-restrained graph of order n and size m.

Publication Type: Journal Article
Publisher: Elsevier BV
Copyright: © 1992 Published by Elsevier B.V.
Item Control Page Item Control Page