Geodesic
Enumerating the digitally convex sets of powers of cycles and Cartesian products of paths and complete graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 859-874 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: convexity, enumeration, digital convexity 
@article{DMGT_2023_43_3_a17,
     author = {Carr, MacKenzie and Mynhardt, Christina M. and Oellermann, Ortrud R.},
     title = {Enumerating the digitally convex sets of powers of cycles and {Cartesian} products of paths and complete graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {859--874},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a17/}
}
TY  - JOUR
AU  - Carr, MacKenzie
AU  - Mynhardt, Christina M.
AU  - Oellermann, Ortrud R.
TI  - Enumerating the digitally convex sets of powers of cycles and Cartesian products of paths and complete graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 859
EP  - 874
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a17/
LA  - en
ID  - DMGT_2023_43_3_a17
ER  - 
%0 Journal Article
%A Carr, MacKenzie
%A Mynhardt, Christina M.
%A Oellermann, Ortrud R.
%T Enumerating the digitally convex sets of powers of cycles and Cartesian products of paths and complete graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 859-874
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a17/
%G en
%F DMGT_2023_43_3_a17
Carr, MacKenzie; Mynhardt, Christina M.; Oellermann, Ortrud R. Enumerating the digitally convex sets of powers of cycles and Cartesian products of paths and complete graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 859-874. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a17/

[1] 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

[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

[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. https://doi.org/10.1016/j.camwa.2011.04.038

[4] 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

[5] 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

[6] 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

[7] 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

[8] 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

[9] 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

[10] 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

[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. https://doi.org/10.1137/070691383

[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. https://doi.org/10.1016/S0020-0255(01)00169-4

[15] 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

[16] N.J.A. Sloane, \textrm{The On-{L}ine {E}ncyclopedia of {I}nteger {S}equences} (2021). https://oeis.org, 2021

[17] 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

[18] 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

[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. https://doi.org/10.1016/j.tcs.2006.09.002