کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419665 | 683850 | 2013 | 7 صفحه PDF | دانلود رایگان |
Let G=(V,E)G=(V,E) be a finite, simple and connected graph. Let S⊆VS⊆V, its closed interval I[S]I[S] is the set of all vertices lying on a shortest path between any pair of vertices of SS. The set SS is geodetic if I[S]=VI[S]=V. The eccentricity of a vertex vv is the number of edges in the greatest shortest path between vv and any vertex ww of GG. The contour Ct(G)Ct(G) of GG is the set formed by vertices vv such that no neighbor of vv has an eccentricity greater than vv. We consider the problem of determining whether the contour of a graph class is geodetic. The diameter diam(G) of GG is the maximum eccentricity of the vertices in VV. In this work we establish a relation between the diameter and the geodeticity of the contour of a graph. We prove that the contour is geodetic for graphs with diameter k≤4k≤4. Furthermore, for every k>4k>4, there is a graph with diameter kk and whose contour is not geodetic. We show that the contour is geodetic for bipartite graphs with diameter k≤7k≤7, and for any k>7k>7 there is a bipartite graph with diameter kk and non-geodetic contour. By applying these results, we solve the open problems mentioned by Cáceres et al. (2008, 2005) [4] and [5] namely to decide whether the contour of cochordal graph, parity graph and bipartite graphs are geodetic.
Journal: Discrete Applied Mathematics - Volume 161, Issues 10–11, July 2013, Pages 1356–1362