×

Reconstructing trees from digitally convex sets. (English) Zbl 1350.05017

Summary: Suppose \(V\) is a finite set and \(\mathcal{C}\) a collection of subsets of \(V\) that contains \(\empty\) and \(V\) and is closed under taking intersections. Then \(\mathcal{C}\) is called a convexity and the ordered pair \((V, \mathcal{C})\) is called an aligned space and the elements of \(\mathcal{C}\) are referred to as convex sets. For a set \(S\subseteq V\), the convex hull of \(S\) relative to \(\mathcal{C}\), denoted by \(\mathrm{CH}_{\mathcal{C}}(S)\), is the smallest convex set containing \(S\). 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\). It is shown that every tree is uniquely determined by its digitally convex sets. These ideas can be used to show that every graph with girth at least 7 is uniquely determined by its digitally convex sets. Given the digitally convex sets of a graph it can be determined efficiently, as a function of the number of convex sets, if these are those of a tree.

MSC:

05C05 Trees
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI

References:

[1] Aigner, M.; Triesch, E., Reconstructing graphs from its neighbourhood lists, Combin. Probab. Comput., 2, 103-113 (1993) · Zbl 0792.05104
[2] 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
[3] Cáceres, J.; Oellermann, O. R., On 3-Steiner simplicial elimination, Discrete Math., 309, 5825-5833 (2009) · Zbl 1221.05042
[4] 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
[5] Chartrand, G.; Lesniak, L.; Zhang, P., Graphs and Digraphs (2010), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton
[6] Dragan, F. F.; Nicolai, F.; Brandstädt, A., Convexity and \(H H D\)-free graphs, SIAM J. Discrete Math., 12, 119-135 (1999) · Zbl 0916.05060
[8] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebr. Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056
[9] Fomin, F. V.; Kratochvil, J.; Lokshtanov, D.; Mancini, F.; Telle, J. A., On the complexity of reconstructing \(H\)-free graphs from their star systems, J. Graph Theory, 68, 113-124 (2011) · Zbl 1230.05215
[11] Kelley, P. J., On isomteric transformations (1942), University of Wisconsin USA, (Ph.D. thesis)
[13] Levenshtein, V. I., A conjecture on the reconstruction of graphs from metric balls of their vertices, Discrete Math., 308, 993-998 (2008) · Zbl 1142.05056
[14] Levenshtein, V. I.; Konstantinova, E.; Konstantinov, E.; Molodtsov, S., Reconstruction of a graph from 2-vicinities of its vertices, Discrete Appl. Math., 156, 1399-1406 (2008) · Zbl 1144.05046
[15] Linial, N., Local-global phenomena, Combin. Probab. Comput., 2, 491-503 (1993) · Zbl 0803.68085
[16] Nielsen, M. H.; Oellermann, O. R., Steiner trees and convex geometries, SIAM J. Discrete Math., 23, 680-693 (2009) · Zbl 1191.05037
[17] Oellermann, O. R., On domination and digital convexity parameters, J. Combin. Math. Combin. Comput., 85, 273-285 (2013) · Zbl 1274.05360
[18] Pfaltz, J. L.; Rosenfeld, A., Sequential operations in digital picture processing, J. ACM, 13, 4, 471-494 (1996) · Zbl 0143.41803
[19] Ulam, S. M., A Collection of Mathematical Problems, 29 (1960), Wiley: Wiley New York · Zbl 0086.24101
[20] Van de Vel, M. J.L., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001
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.