Journal article
Graphs of maximum diameter
Discrete Mathematics, Vol.102(2), pp.121-141
1992
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.
Details
- Title
- Graphs of maximum diameter
- Authors/Creators
- L. Caccetta (Author/Creator) - Curtin UniversityW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Discrete Mathematics, Vol.102(2), pp.121-141
- Publisher
- Elsevier BV
- Identifiers
- 991005543371407891
- Copyright
- © 1992 Published by Elsevier B.V.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
Source: InCites
Metrics
130 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 2 Chemistry
- 2.123 Protein Stucture, Folding & Modelling
- 2.123.778 QSAR
- Web Of Science research areas
- Mathematics
- ESI research areas
- Mathematics