Article in volume
Authors:
Ortrud R. Oellermann
Department of Mathematics and StatisticsUniversity of WinnipegManitoba R3B 2E9CANADA
email: o.oellermann@uwinnipeg.ca
Title:
Enumerating the digitally convex sets of powers of cycles and Cartesian products of paths and complete graphs
PDFSource:
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 , https://doi.org/10.7151/dmgt.2407
Abstract:
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.
Keywords:
convexity, enumeration, digital convexity
References:
- J.I. Brown and O.R. Oellermann, Graphs with a minimal number of convex sets, Graphs Combin. 30 (2014) 1383–1397.
https://doi.org/10.1007/s00373-013-1356-2 - J.I. Brown and O.R. Oellermann, On the spectrum and number of convex sets in graphs, Discrete Math. 338 (2015) 1144-1153.
https://doi.org/10.1016/j.disc.2015.01.024 - 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.
https://doi.org/10.1016/j.camwa.2011.04.038 - J. Cáceres and O.R. Oellermann, On $3$-{S}teiner simplicial orderings, Discrete Math. 309 (2009) 5828–5833.
https://doi.org/10.1016/j.disc.2008.05.047 - J. Cáceres, O.R. Oellermann and M.L. Puertas, Minimal trees and monophonic convexity, Discuss. Math. Graph Theory 32 (2012) 685–704.
https://doi.org/10.7151/dmgt.1638 - M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999) 91–95.
https://doi.org/10.1016/S0012-365X(98)00394-X - F.F. Dragan, F. Nicolai and A. Brandstädt, Convexity and {HHD}-free graphs, SIAM J. Discrete Math. 12 (1999) 119–135.
https://doi.org/10.1137/S0895480195321718 - R. Euler, P. Oleksik and Z. Skupień, Counting maximal distance-independent sets in grid graphs, Discuss. Math. Graph Theory 33 (2013) 531–557.
https://doi.org/10.7151/dmgt.1707 - M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Meth. 7 (1986) 433–444.
https://doi.org/10.1137/0607049 - P. Lafrance, O.R. Oellermann and T. Pressey, Generating and enumerating digitally convex sets of trees, Graphs Combin. 32 (2016) 721–732.
https://doi.org/10.1007/s00373-015-1604-8 - E. Munarini and N.Z. Salvi, Circular binary strings without zigzags, Integers 3 (2003) #A19.
- M.H. Nielsen and O.R. Oellermann, Steiner Trees and Convex Geometries, SIAM J. Discrete Math. 23 (2009) 690–693.
https://doi.org/10.1137/070691383 - O.R. Oellermann, On domination and digital convexity parameters, J. Combin. Math. Combin. Comput. 85 (2013) 273–285.
- J.L. Pfaltz and R.E. Jamison, Closure systems and their structure, Inform. Sci. 139 (2001) 275–286.
https://doi.org/10.1016/S0020-0255(01)00169-4 - A. Rosenfeld and J.L. Pfaltz, Sequential operations in digital picture processing, J. ACM 13 (1966) 471–494.
https://doi.org/10.1145/321356.321357 - N.J.A. Sloane, The On-{L}ine {E}ncyclopedia of {I}nteger {S}equences (2021).
https://oeis.org, 2021 - L.A. Székely and H. Wang, On subtrees of trees, Adv. Appl. Math. 34 (2005) 138–155.
https://doi.org/10.1016/j.aam.2004.07.002 - L.A. Székely and H. Wang, Binary trees with the largest number of subtrees, Discrete Appl. Math. 155 (2007) 374–385.
https://doi.org/10.1016/j.dam.2006.05.008 - M.L.J. van de Vel, Theory of Convex Structures (North-Holland, 1993).
- W. Yan and Y.N. Yeh, Enumeration of subtrees of trees, Theoret. Comput. Sci. 369 (2006) 256–268.
https://doi.org/10.1016/j.tcs.2006.09.002
Close