DSpace About DSpace Software

Dyuthi @ CUSAT >
Computer Applications >
Faculty >
Dr. Kannan Balakrishnan >

Please use this identifier to cite or link to this item: http://purl.org/purl/4197

Title: On the remoteness function in median graphs
Authors: Kannan, Balakrishnan
Boštjan, Brešar
Manoj, Changat
Wilfried, Imrich
Sandi, Klavzar
Matja, Kovse
Ajitha, Subhamathi R
Keywords: Hypercube
Median graph
Median set
Remoteness function
Geodetic number
Periphery transversal
Issue Date: 22-Aug-2009
Publisher: Elsevier
Abstract: A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x 2 V.G/ the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O.mlog n/ time whether G is a median graph with geodetic number 2
Description: Discrete Applied Mathematics 157 (2009) 3679- 3688
URI: http://dyuthi.cusat.ac.in/purl/4197
Appears in Collections:Dr. Kannan Balakrishnan

Files in This Item:

File Description SizeFormat
On the remoteness function in median graphs.pdfpdf595.27 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback