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
Kannan, Balakrishnan; Manoj, Changat; Henry, Martyn Mulder(Econometric Institute Research Papers, September 15, 2006)
[+]
[-]
Abstract:
The Majority Strategy for finding medians of a set of clients on a graph
can be relaxed in the following way: if we are at v, then we move to a neighbor
w if there are at least as many clients closer to w than to v (thus ignoring the
clients at equal distance from v and w). The graphs on which this Plurality
Strategy always finds the set of all medians are precisely those for which the
set of medians induces always a connected subgraph
Description:
Report/Econometric Institute, Erasmus University Rotterdam