ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


M. Carr

MacKenzie Carr

University of Victoria


C.M. Mynhardt

Christina M. Mynhardt

University of Victoria, Victoria



O.R. Oellermann

Ortrud R. Oellermann

Department of Mathematics and StatisticsUniversity of WinnipegManitoba R3B 2E9CANADA




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



Discussiones Mathematicae Graph Theory 43(3) (2023) 859-874

Received: 2020-08-06 , Revised: 2021-03-26 , Accepted: 2021-03-26 , Available online: 2021-05-04 ,


Given a finite set $V$, a convexity, $\mathscr{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 $\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\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\geq 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 × m$ binary arrays.


convexity, enumeration, digital convexity


  1. J.I. Brown and O.R. Oellermann, Graphs with a minimal number of convex sets, Graphs Combin. 30 (2014) 1383–1397.
  2. J.I. Brown and O.R. Oellermann, On the spectrum and number of convex sets in graphs, Discrete Math. 338 (2015) 1144-1153.
  3. J. Cáceres, A. Márquez, M. Morales and M.L. Puertas, Towards a new framework for domination, Comput. Math. Appl. 62 (2011) 44–50.
  4. J. Cáceres and O.R. Oellermann, On $3$-{S}teiner simplicial orderings, Discrete Math. 309 (2009) 5828–5833.
  5. J. Cáceres, O.R. Oellermann and M.L. Puertas, Minimal trees and monophonic convexity, Discuss. Math. Graph Theory 32 (2012) 685–704.
  6. M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999) 91–95.
  7. F.F. Dragan, F. Nicolai and A. Brandstädt, Convexity and {HHD}-free graphs, SIAM J. Discrete Math. 12 (1999) 119–135.
  8. R. Euler, P. Oleksik and Z. Skupień, Counting maximal distance-independent sets in grid graphs, Discuss. Math. Graph Theory 33 (2013) 531–557.
  9. M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Meth. 7 (1986) 433–444.
  10. P. Lafrance, O.R. Oellermann and T. Pressey, Generating and enumerating digitally convex sets of trees, Graphs Combin. 32 (2016) 721–732.
  11. E. Munarini and N.Z. Salvi, Circular binary strings without zigzags, Integers 3 (2003) #A19.
  12. M.H. Nielsen and O.R. Oellermann, Steiner Trees and Convex Geometries, SIAM J. Discrete Math. 23 (2009) 690–693.
  13. O.R. Oellermann, On domination and digital convexity parameters, J. Combin. Math. Combin. Comput. 85 (2013) 273–285.
  14. J.L. Pfaltz and R.E. Jamison, Closure systems and their structure, Inform. Sci. 139 (2001) 275–286.
  15. A. Rosenfeld and J.L. Pfaltz, Sequential operations in digital picture processing, J. ACM 13 (1966) 471–494.
  16. N.J.A. Sloane, The On-{L}ine {E}ncyclopedia of {I}nteger {S}equences (2021)., 2021
  17. L.A. Székely and H. Wang, On subtrees of trees, Adv. Appl. Math. 34 (2005) 138–155.
  18. L.A. Székely and H. Wang, Binary trees with the largest number of subtrees, Discrete Appl. Math. 155 (2007) 374–385.
  19. M.L.J. van de Vel, Theory of Convex Structures (North-Holland, 1993).
  20. W. Yan and Y.N. Yeh, Enumeration of subtrees of trees, Theoret. Comput. Sci. 369 (2006) 256–268.