Ricerc@Sapienza

Let G be a graph, u and v two vertices of G, and X a subset of V(G). A u-v geodesic is a path between u and v of minimum length. Ig(u,v) is the set of vertices that lie on any u-v geodesic and Ig(X) is the set ⋃u,v∈XIg(u,v). X is g-convex if Ig(X)=X. Analogously, Im(u,v) is the set of vertices that lie on any induced path between u and v and Im(X) is the set ⋃u,v∈XIm(u,v). X is m-convex if Im(X)=X. The g-convex hull [X]g of X is the smallest g-convex set containing X. Igh(X) equals Ig(X), if h=1, and equals I(Igh−1(X)), if h>1. The geodetic iteration number, gin(X), of X in G is the smallest h such that Igh(X)=Igh+1(X)=[X]g. The geodetic iteration number of G, denoted by gin(G), is defined as gin(G)=maxgin(X)|X⊆V(G). In this paper we provide an O(n3m) time algorithm (where n and m are the cardinalities of the vertex set and of the edge set of the graph, respectively) to compute the geodetic iteration number of a graph belonging to the class, say Γ, of graphs in which the families of g-convex sets and of m-convex sets coincide (i.e., every g-convex set is m-convex). Since Γ properly contains the class of distance-hereditary graphs, this result extends the result in Dourado et al. (2016). Furthermore, we provide an O(n2m) time algorithm to compute the geodetic iteration number of a bipartite distance-hereditary graph.