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
Voir la notice de l'article provenant de la source Library of Science
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},
publisher = {mathdoc},
volume = {43},
number = {3},
year = {2023},
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 PB - mathdoc 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 %I mathdoc %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/