Partitions and covers in $\hat{I}”$ convexity

Abstract

Given a graph $G$ and a set $S\subseteq V(G)$, we say that $S$ is $\hat{I}”$-convex if the neighborhood of every vertex not in $S$ is an independent set. A collection $\mathcal{V}=(V_1,V_2,\dots ,V_p)$ of convex sets of $G$ is a convex $p$-cover if $V(G)=\bigcup _{1\le i\le p}{V}_i$ and $V_i⊈\bigcup _{1\le j\le p,j\ne i}{V}_j$ for $i\in \{1,\dots ,p\}$. If the convex sets of $\mathcal{V}$ are pairwise disjoint, $\mathcal{V}$ is a convex $p$-partition of $V(G)$. The convex cover number $\ddot{I}{•}_c(G)$ (the convex partition number $\hat{I}{˜}_c(G)$) of a graph $G$ is the least integer $p\ge 2$ for which $G$ has a convex $p$-cover (convex $p$-partition). In this work, we prove that the {\sc Convex p-cover} and {\sc Convex p-Partition} problems are \NP-complete for any fixed $p\ge 4$ in $\hat{I}”$-convexity. Furthermore, for the three standard graph products, namely, the Cartesian, strong and lexicographic products, we determine these parameters for some cases and present bounds for others.