On the contour of graphs

• Published in: Discrete Applied Mathematics 2013-07, Vol.161 (10-11), p.1356-1362
• Main Authors: Artigas, D., Dantas, S., Dourado, M.C., Szwarcfiter, J.L., Yamaguchi, S.
• Format: Article
• Language: English
• Subjects: Bipartite graphs; Contour; Convexity; Eccentricity; Geodetic set; Graphs; Intervals; Mathematical analysis; Parity; Shape; Shortest-path problems
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2012.12.024

Let G=(V,E) be a finite, simple and connected graph. Let S⊆V, its closed interval I[S] is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if I[S]=V. The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G. The contour Ct(G) of G is the set formed by vertices v such that no neighbor of v has an eccentricity greater than v. We consider the problem of determining whether the contour of a graph class is geodetic. The diameter diam(G) of G is the maximum eccentricity of the vertices in V. 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≤4. Furthermore, for every k>4, there is a graph with diameter k and whose contour is not geodetic. We show that the contour is geodetic for bipartite graphs with diameter k≤7, and for any k>7 there is a bipartite graph with diameter k and non-geodetic contour. By applying these results, we solve the open problems mentioned by Cáceres et al. (2008, 2005) [4,5] namely to decide whether the contour of cochordal graph, parity graph and bipartite graphs are geodetic.