Enumerating the Digitally Convex Sets of Powers of Cycles and Cartesian Products of Paths and Complete Graphs

Abstract

Given a finite set $V$, a convexity $\mathcal{C}$, is a collection of subsets of $V$ that contains both the empty set and the set $V$ and is closed under intersections. The elements of $\mathcal{C}$ are called convex sets. The digital convexity, originally proposed as a tool for processing digital images, is defined as follows: a subset $S\subseteq V(G)$ is digitally convex if, for every $v\in V(G)$, we have $N[v]\subseteq N[S]$ implies $v\in S$. The number of cyclic binary strings with blocks of length at least $k$ is expressed as a linear recurrence relation for $k\ge 2$. A bijection is established between these cyclic binary strings and the digitally convex sets of the $(k-1{)}^{th}$ power of a cycle. A closed formula for the number of digitally convex sets of the Cartesian product of two complete graphs is derived. A bijection is established between the digitally convex sets of the Cartesian product of two paths, $P_n\square P_m$, and certain types of $n\times m$ binary arrays.

16 pages, 3 figures, 1 table