Now showing items 1-2 of 2
| 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 |
| Files | Size |
|---|---|
| Median Graphs, ... nd Geodetic Number Two.pdf | (256.4Kb) |
| Abstract: | The set of vertices that maximize (minimize) the remoteness is the antimedian (median) set of the profile. It is proved that for an arbitrary graph G and S V (G) it can be decided in polynomial time whether S is the antimedian set of some profile. Graphs in which every antimedian set is connected are also considered. |
| URI: | http://dyuthi.cusat.ac.in/purl/4217 |
| Files | Size |
|---|---|
| On the generali ... blemantimedian subsets.pdf | (142.4Kb) |
Now showing items 1-2 of 2
Dyuthi Digital Repository Copyright © 2007-2011 Cochin University of Science and Technology. Items in Dyuthi are protected by copyright, with all rights reserved, unless otherwise indicated.