A periphery transversal of a median graph G is introduced as a set of vertices
that meets all the peripheral subgraphs of G. Using this concept, median graphs
with geodetic number 2 are characterized in two ways. They are precisely
the median graphs that contain a periphery transversal of order 2 as well as
the median graphs for which there exists a profile such that the remoteness
function is constant on G. Moreover, an algorithm is presented that decides
in O(mlog n) time whether a given graph G with n vertices and m edges is a
median graph with geodetic number 2. Several additional structural properties
of the remoteness function on hypercubes and median graphs are obtained and
some problems listed
Description:
University of Ljubljana
Institute of Mathematics, Physics and Mechanics
Department of Mathematics
Preprint series, Vol. 46 (2008), 1046