Partitioning a graph into convex sets

Let G be a finite simple graph. Let S ⊆ V ( G ) , its closed interval I [ S ] is the set of all vertices lying on shortest paths between any pair of vertices of S . The set S is convex if I [ S ] = S . In this work we define the concept of a convex partition of graphs. If there exists a partition of V ( G ) into p convex sets we say that G is p -convex. We prove that it is N P -complete to decide whether a graph G is p -convex for a fixed integer p ≥ 2 . We show that every connected chordal graph is p -convex, for 1 ≤ p ≤ n . We also establish conditions on n and k to decide if the k -th power of a cycle C n is p -convex. Finally, we develop a linear-time algorithm to decide if a cograph is p -convex.