Enumerating the digitally convex sets of powers of cycles and Cartesian products of paths and complete graphs

Carr, MacKenzie  ; Mynhardt, Christina M. ; Oellermann, Ortrud R.

Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 859-874

Résumé

Given a finite set V, a convexity, 𝒞, 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 𝒞 are called convex sets. The digital convexity, originally proposed as a tool for processing digital images, is defined as follows: a subset S⊆ V(G) is digitally convex if, for every v∈ V(G), we have N[v]⊆ N[S] implies v∈ S. The number of cyclic binary strings with blocks of length at least k is expressed as a linear recurrence relation for k≥ 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 □ P_m, and certain types of n × m binary arrays.

Détail

Keywords: convexity, enumeration, digital convexity