×

Generating and enumerating digitally convex sets of trees. (English) Zbl 1338.05042

Summary: A set \(S\) of vertices in a graph \(G\) with vertex set \(V\) is digitally convex if for every vertex \(v \in V\), \(N[v] \subseteq N[S]\) implies \(v \in S\). We show that a vertex belongs to at most half of the digitally convex sets of a graph. Moreover, a vertex belongs to exactly half of the digitally convex sets if and only if it is simplicial. An algorithm that generates all digitally convex sets of a tree is described and sharp upper and lower bounds for the number of digitally convex sets of a tree are obtained. A closed formula for the number of digitally convex sets of a path is derived. It is shown how a binary cotree of a cograph can be used to enumerate its digitally convex sets in linear time.

MSC:

05C05 Trees
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM monographs on discrete mathematics and applications. SIAM, Philadelphia (2004)
[2] Brown, J., Oellermann, O.R.: Graphs with a minimal number of convex sets. Graphs Comb. 30, 1383-1397 (2014) · Zbl 1306.05041
[3] Brown, J., Oellermann, O.R.: On the spectrum and number of convex sets of a graph. Discret. Math. 338, 1144-1153 (2015) · Zbl 1309.05116
[4] Cáceres, J., Márquez, A., Morales, M., Puertas, M.L.: Towards a new framework for domination. Comput. Math. Appl. 62, 44-50 (2011) · Zbl 1228.05223
[5] Cáceres, J., Oellermann, O.R.: On \[33\]-Steiner simplicial elimination. Discret. Math. 309, 5825-5833 (2009) · Zbl 1221.05042
[6] Cáceres, J., Oellermann, O.R., Puertas, M.L.: Minimal trees and monophonic convexity. Discuss. Math. Graph Theory 32, 685-704 (2012) · Zbl 1293.05314
[7] Corneil, D.G., Lerchs, H., Stewart-Burlingham, L.: Complement reducible graphs. Discret. Appl. Math. 3, 163-174 (1981) · Zbl 0463.05057
[8] Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926-934 (1985) · Zbl 0575.68065
[9] Dragan, F.F., Nicolai, F., Brandstädt, A.: Convexity and \[HHD\] HHD-free graphs. SIAM J. Discret. Math. 12, 119-135 (1999) · Zbl 0916.05060
[10] Farber, M., Jamison, R.E.: Convexity in graphs and hypergraphs. SIAM J. Algebr. Discret. Method 7, 433-444 (1986) · Zbl 0591.05056
[11] Jamison, R.E., Pfaltz, J.L.: Closure systems and their structure. Inf. Sci. 139, 275-286 (2001) · Zbl 0993.06004
[12] Nielsen, M.H., Oellermann, O.R.: Steiner trees and convex geometries. SIAM J. Discret. Math. 23, 680-693 (2009) · Zbl 1191.05037
[13] Oellermann, O.R.: On domination and digital convexity parameters. JCMCC 85, 273-285 (2013) · Zbl 1274.05360
[14] Pfaltz, J.L., Rosenfeld, A.: Sequential operations in digital picture processing. J. ACM 13(4), 471-494 (1996) · Zbl 0143.41803
[15] Székely, L.A., Wang, H.: On subtrees of trees. Adv. Appl. Math. 34(1), 138-155 (2005) · Zbl 1153.05019
[16] Székely, L.A., Wang, H.: Binary trees with the largest number of subtrees. Discret. Appl. Math. 155(3), 374-385 (2007) · Zbl 1113.05025
[17] Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 410-421 (1979) · Zbl 0419.68082
[18] Van de Vel, M.J.L.: Theory of Convex Structures. North-Holland, Amsterdam (1993) · Zbl 0785.52001
[19] Yan, W., Yeh, Y.-N.: Enumeration of subtrees of trees. Theor. Comput. Sci. 369, 256-268 (2006) · Zbl 1140.05308
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.