# Graphs of maximum diameter

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

*No subscription required

## Abstract

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. |

URI: | http://researchrepository.murdoch.edu.au/id/eprint/27454 |

Item Control Page |