The strong convexity spectra of grids

Abstract

Let $D$ be a connected oriented graph. A set $S\subseteq V(D)$ is convex in $D$ if, for every pair of vertices $x,y\in S$, the vertex set of every $xy$-geodesic, ($xy$ shortest directed path) and every $yx$-geodesic in $D$ is contained in $S$. The convexity number, $\mathrm{con}(D)$, of a non-trivial oriented graph, $D$, is the maximum cardinality of a proper convex set of $D$. The strong convexity spectrum of the graph $G$, $S_{SC}(G)$, is the set $\{\mathrm{con}(D):D\mathrm{is}\mathrm{a}\mathrm{strong}\mathrm{orientation}\mathrm{of}G\}$. In this paper we prove that the problem of determining the convexity number of an oriented graph is $\mathcal{NP}$-complete, even for bipartite oriented graphs of arbitrary large girth, extending previous known results for graphs. We also determine $S_{SC}(P_n\square P_m)$, for every pair of integers $n,m\ge 2$.

32 pages, 16 figures