Let G be a finite simple graph. Let S ⊆ V (G), 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 convex if I[S] = S. In this work we define the concept of 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 is NP -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 a power of cycle is p-convex. Finally, we develop a linear-time algorithm to decide if a cograph is p-convex.
Artigas et al. REF show that every connected chordal graph G = (V, E) is k-convex, for 1 ≤ k ≤ |V |.
Partitioning a graph into convex sets
Discret. Math.
Discret. Math.
Computer Science Mathematics