Graphs of maximum diameter (Q1193709)

A \(K\)-restrained graph is a simple connected graph of minimum degree at least \(K\). This includes all \(K\)-connected, all \(K\)-edge-connected and all connected \(K\)-regular graphs. This paper derives first tight upper bounds on the diameter of graphs within each of these families for fixed number of nodes (order) and secondly tight upper bounds on the number of edges (size) in \(K\)-restrained graphs with given order and diameter. This leads to the determination of the maximum diameter of \(K\)-restrained graphs with given order and size.