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.
Mezzini, M., Moscarini, M. (2015). On the geodeticity of the contour of a graph. DISCRETE APPLIED MATHEMATICS, 181, 208-220 [10.1016/j.dam.2014.08.028].
On the geodeticity of the contour of a graph
MEZZINI, MAURO
;
2015-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.