Article ID Journal Published Year Pages File Type
419000 Discrete Applied Mathematics 2015 12 Pages PDF
Abstract

The eccentricity   of a vertex vv in a graph GG is the maximum distance of vv from any other vertex of GG and vv is a contour vertex   of GG if each vertex adjacent to vv has eccentricity not greater than the eccentricity of vv. The set of contour vertices of GG is geodetic   if every vertex of GG lies on a shortest path between a pair of contour vertices. In this paper, we firstly investigate the existence of operations on graphs that allow to construct graphs in which the contour is geodetic. Then, after providing an alternative proof of the fact that the contour is geodetic in every HHD-free graph, we show that the contour is geodetic in every cactus and in every graph whose blocks are HHD-free or cycles or cographs. Finally, we generalize the above result by introducing the concept of geodetic-contour-preserving   class of graphs and by proving that, if each block BB in a graph GG belongs to a class GBGB of graphs which is geodetic-contour-preserving, then the contour of GG is geodetic.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,