Reconstruction of Rooted Directed Trees

Keywords: tree reconstruction, subtree size frequencies, rooted directed trees

Abstract

Let T be a rooted directed tree on n vertices, rooted at v. The rooted subtree frequency vector (RSTF-vector) of T with root v, denoted by rstf(T, v) is a vector of length n whose entry at position k is the number of subtrees of T that contain v and have exactly k vertices. In this paper we present an algorithm for reconstructing rooted directed trees from their rooted subtree frequencies (up to isomorphism). We show that there are examples of nonisomorphic pairs of rooted directed trees that are RSTF-equivalent, s.t. they share the same rooted subtree frequency vectors. We have found all such pairs (groups) for small sizes by using exhaustive computer search. We show that infinitely many nonisomorphic RSTF-equivalent pairs of trees exist by constructing infinite families of examples.

Downloads

Download data is not yet available.

References

Acharya, Jayadev, Das, Hirakendu, Milenkovic, Olgica, Orlitsky, Alon, and Pan, Shengjun. String reconstruction from substring compositions. SIAM Journal on Discrete Mathematics, 29(3):1340–1371, 2015. DOI: 10.1137/140962486.

Bartha, Dénes and Burcsi, Péter. Reconstructibility of trees from subtree size frequencies. Studia Universitatis Babes-Bolyai, Mathematica, 59(4):435–442, 2014.

Dudik, Miroslav and Schulman, Leonard J. Reconstruction from subsequences. Journal of Combinatorial Theory, Series A, 103(2):337-348, 2003. DOI: 10.1016/s0097-3165(03)00103-1.

Kós, Géza, Ligeti, Péter, and Sziklai, Péter. Reconstruction of matrices from submatrices. Mathematics of Computation, 778:1733–1747, 2009. DOI: 10.1090/s0025-5718-09-02210-8.

Krasikov, I. and Roditty, Y. On a reconstruction problem for sequences. Journal of Combinatorial Theory, Series A, 77(2):344–348, 1997. DOI: 10.1006/jcta.1997.2732.

Lenstra, A. K., Lenstra, H. W., and Lovász, L. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. DOI: 10.1007/bf01457454.

Manvel, Bennet. Reconstruction of trees. Canadian Journal of Mathematics, 22(1):55–60, 1970. DOI: 10.4153/CJM-1970-007-4.

Manvel, Bennet. On reconstructing graphs from their sets of subgraphs. Journal of Combinatorial Theory, Series B, 21(2):156–165, 1976. DOI: 10.1016/0095-8956(76)90056-3.

Manvel, Bennet and Stockmeyer, Paul K. On reconstruction of matrices. Mathematics Magazine, 44(4):218–221, 1971. DOI: 10.2307/2689082.

Published
2019-11-03
How to Cite
Bartha, D. (2019). Reconstruction of Rooted Directed Trees. Acta Cybernetica, 24(2), 249-262. https://doi.org/10.14232/actacyb.24.2.2019.5
Section
Regular articles