School Seminars and Colloquia

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

ORSUM Seminar

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