کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419000 681731 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the geodeticity of the contour of a graph
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the geodeticity of the contour of a graph
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 181, 30 January 2015, Pages 209–220
نویسندگان
, ,