1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

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

Published Online: 17 Jun 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 06 Aug 2020
Accepted: 26 Mar 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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 (G), we have N[v] ⊆ N[S] implies ν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, PnPm, and certain types of n × m binary arrays.

Keywords

MSC 2010

[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-210.1007/s00373-013-1356-2Search in Google Scholar

[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.02410.1016/j.disc.2015.01.024Search in Google Scholar

[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.03810.1016/j.camwa.2011.04.038Search in Google Scholar

[4] J. Cáceres and O.R. Oellermann, On 3-Steiner simplicial orderings, Discrete Math. 309 (2009) 5828–5833. https://doi.org/10.1016/j.disc.2008.05.04710.1016/j.disc.2008.05.047Search in Google Scholar

[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.163810.7151/dmgt.1638Search in Google Scholar

[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-X10.1016/S0012-365X(98)00394-XSearch in Google Scholar

[7] F.F. Dragan, F. Nicolai and A. Brandst¨adt, Convexity and HHD-free graphs, SIAM J. Discrete Math. 12 (1999) 119–135. https://doi.org/10.1137/S089548019532171810.1137/S0895480195321718Search in Google Scholar

[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.170710.7151/dmgt.1707Search in Google Scholar

[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/060704910.1137/0607049Search in Google Scholar

[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-810.1007/s00373-015-1604-8Search in Google Scholar

[11] E. Munarini and N.Z. Salvi, Circular binary strings without zigzags, Integers 3 (2003) #A19.Search in Google Scholar

[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/07069138310.1137/070691383Search in Google Scholar

[13] O.R. Oellermann, On domination and digital convexity parameters, J. Combin. Math. Combin. Comput. 85 (2013) 273–285.Search in Google Scholar

[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-410.1016/S0020-0255(01)00169-4Search in Google Scholar

[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.32135710.1145/321356.321357Search in Google Scholar

[16] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences (2021). https://oeis.org, 2021Search in Google Scholar

[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.00210.1016/j.aam.2004.07.002Search in Google Scholar

[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.00810.1016/j.dam.2006.05.008Search in Google Scholar

[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.00210.1016/j.tcs.2006.09.002Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo