An antimedian of a pro le = (x1; x2; : : : ; xk) of vertices of a graph G is a
vertex maximizing the sum of the distances to the elements of the pro le. The
antimedian function is de ned on the set of all pro les on G and has as output
the set of antimedians of a pro le. It is a typical location function for nding a
location for an obnoxious facility. The `converse' of the antimedian function is the
median function, where the distance sum is minimized. The median function is
well studied. For instance it has been characterized axiomatically by three simple
axioms on median graphs. The median function behaves nicely on many classes
of graphs. In contrast the antimedian function does not have a nice behavior on
most classes. So a nice axiomatic characterization may not be expected. In this
paper such a characterization is obtained for the two classes of graphs on which
the antimedian is well-behaved: paths and hypercubes.
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