Computational and structural analysis of the contour of graphs

Let G = ( V , E ) be a finite, simple, and connected graph. The closed interval I [ S ] of a set S ⊆ V 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 . A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v . The contour C t ( G ) of G is the set formed by the contour vertices of G . We consider two problems: ( a ) the problem of determining whether the contour of a graph class is geodetic; ( b ) the problem of determining if there exists a graph such that I [ C t ( G ) ] is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem ( a ) and show two infinite families such that C t ( G ) is not geodetic. Using computational tools, we establish the minimum graphs for which C t ( G ) is not geodetic; and show that all graphs with | V | < 13 , and all bipartite graphs with | V | < 18 , are such that I [ C t ( G ) ] is geodetic.