Abstract.
A graph is radially maximal if its radius decreases after the addition
of any edge of its complement.
We prove that this class of graphs is rich, in the sense that every graph
G is an induced subgraph of some radially maximal graph.
Further, we discuss the number of cut-vertices in radially maximal graphs of
radius r.
-
If r is less than 3 then the radially maximal graph of radius
r does not contain cut-vertices.
-
If r equals 3 then the radially maximal graph of radius
r contains at most 2 cut-vertices.
-
If r is greather than 3 then for any prescribed number k there
are infinitely many radially maximal graphs of radius r having
exactly k cut-vertices.
These results seem to be surprising, since one would guess that if a graph
is radially maximal, then it is either a very dense graph or a graph which
is in some sense "regular".