# Unicyclic and non-selfcentric radially-maximal graphs with minimum number of vertices

*by Dr Martin Knor *

*Institution:*Slovak University of Technology

*Date: Tue 9th December 2008*

*Time: 1:05 PM*

*Location: Room 213, Richard Berry Bldg, The University of Melbourne*

*Abstract*: A graph is radially-maximal if adding any edge from its complement decreases its radius. Intuitively, radially-maximal graphs should be either very dense or symmetric.

Therefore it is interesting that there exist unicyclic and non-selfcentric radially-maximal graphs.

(A graph is non-selfcentric if its radius is strictly smaller than its diameter.) In this talk we characterize unicyclic non-selfcentric radially-maximal graphs on the minimum number of vertices.

Such graphs must have radius r at least 5, order 3r-1, unique cycle of length 2r-2 and exactly 4 rays attached to the cycle. This characterization is the first step towards proving a more general conjecture on non-selfcentric radially-maximal graphs.

*For More Information:* Mark Fackrell mfackrel@ms.unimelb.edu.au