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

preprint2020arXivOpen access

Abstract

Given a finite set VV, a convexity C\mathscr{C}, is a collection of subsets of VV that contains both the empty set and the set VV and is closed under intersections. The elements of C\mathscr{C} 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)S\subseteq V(G) is digitally convex if, for every v∈V(G)v\in V(G), we have N[v]⊆N[S]N[v]\subseteq N[S] implies v∈Sv\in S. The number of cyclic binary strings with blocks of length at least kk is expressed as a linear recurrence relation for k≥2k\geq 2. A bijection is established between these cyclic binary strings and the digitally convex sets of the (k−1)th(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, Pn□PmP_n \square P_m, and certain types of n×mn \times m binary arrays.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.