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. An induced connected subgraph HH of GG is isometric if, every two vertices of HH, have in HH the same distance as in GG. A graph is bridged if it does not contains an isometric cycle with length greater than 3. In this note, we show that the contour of a bridged graph is geodetic.
Mezzini, M., M., M. (2015). The contour of a bridged graph is geodetic. DISCRETE APPLIED MATHEMATICS, 204, 213-215 [10.1016/j.dam.2015.10.007].
The contour of a bridged graph is geodetic
Mauro Mezzini
;
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. An induced connected subgraph HH of GG is isometric if, every two vertices of HH, have in HH the same distance as in GG. A graph is bridged if it does not contains an isometric cycle with length greater than 3. In this note, we show that the contour of a bridged graph is geodetic.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
