|
Dyuthi @ CUSAT >
e-SCHOLARSHIP >
Computer Applications >
Faculty >
Dr. Kannan Balakrishnan >
Please use this identifier to cite or link to this item:
http://purl.org/purl/4237
|
| Title: | Median graphs, the remoteness function, periphery transversals, and geodetic number two |
| Authors: | Kannan, Balakrishnan
Bostjan, Brešar
Manoj, Changat
Wilfried, Imrich
Sandi, Klavzar
Matjaz, Kovse
Ajitha, Subhamathi R |
| Keywords: | median graph
median set
remoteness function
geodetic number
periphery transversal
hypercube |
| Issue Date: | 25-Mar-2008 |
| 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 |
| ISSN: | 1318-4865 |
| Appears in Collections: | Dr. Kannan Balakrishnan
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|
