Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Graphs of maximum diameter

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

Free to read:
*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.

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