On local convexity in graphs (Q1089354)

Two types of convexity in graphs are studied. A set K of vertices of an undirected graph G is g-convex (or m-convex) if for every pair x, y of vertices of K all vertices of all shortest (or chordless respectively) paths between x and y are also in K. The closed neighbourhood \(N^ j[S]\) of radius j of a subset S of the vertex set of G is the set of all vertices of G whose distance from at least one vertex of S is less than or equal to j. For \(j=1\) it is written simply N[S], for \(S=\{v\}\) it is \(N^ j[v]\). Various types of local convexity are investigated, namely: if N[v] is convex for every vertex v; if \(N^ j[v]\) is convex for every vertex v and every number j; if N[K] is convex for every convex subset K; if \(N^ j[K]\) is convex for every convex subset K and every number j. Properties of graphs satisfying such conditions are studied (including the questions of computational complexity of recognizing).