|
Title:
|
Median graphs, the remoteness function, periphery transversals, and geodetic number two |
|
Author:
|
Kannan, Balakrishnan; Bostjan, Brešar; Manoj, Changat; Wilfried, Imrich; Sandi, Klavzar; Matjaz, Kovse; Ajitha, Subhamathi R
|
|
Abstract:
|
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 |
|
URI:
|
http://dyuthi.cusat.ac.in/purl/4237
|
|
Date:
|
2008-03-25 |