Geodesic
Classification of trees whose maximal subtrees are all isomorphic
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 135-137.

Voir la notice de l'article provenant de la source Math-Net.Ru

Trees are an important class of graphs that are used in various applications. One of these problems is the problem of restoring a system from its known subsystems. Known problems of reconstructibility with respect to the list of maximal subgraphs (Kelly — Ulam conjecture) and the list of pairwise non-isomorphic maximal subgraphs (Harary conjecture) for trees have a solution: each tree is determined, up to isomorphism, by the set of its maximal subgraphs (Kelly's theorem) and by the set of its pairwise non-isomorphic maximal subgraphs (Harari — Palmer theorem). Harary and Palmer also proved a stronger result: every tree is determined, up to isomorphism, by its maximal subtrees, that is, the trees obtained by removing one leaf from the original tree. Finally, Manvel proved that all but four trees are determined, up to isomorphism, by their pairwise non-isomorphic maximal subtrees. The paper considers the problem of describing trees whose maximal subtrees are all isomorphic. A characteristic theorem is given for such trees: all maximal subtrees of a tree are isomorphic if and only if all its leaves are similar. A class of multilevel stars is introduced. It is proved that this class coincides with the class of trees whose all maximal subtrees are isomorphic.
Keywords: graph, tree, reconstructibility. 
@article{PDMA_2024_17_a33,
     author = {M. B. Abrosimov and D. A. Tomilov},
     title = {Classification of trees whose maximal subtrees are all isomorphic},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {135--137},
     publisher = {mathdoc},
     number = {17},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a33/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - D. A. Tomilov
TI  - Classification of trees whose maximal subtrees are all isomorphic
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 135
EP  - 137
IS  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a33/
LA  - ru
ID  - PDMA_2024_17_a33
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A D. A. Tomilov
%T Classification of trees whose maximal subtrees are all isomorphic
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 135-137
%N 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a33/
%G ru
%F PDMA_2024_17_a33
M. B. Abrosimov; D. A. Tomilov. Classification of trees whose maximal subtrees are all isomorphic. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 135-137. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a33/

[1] Oumazouz Z., Karim D., “A new symmetric key cryptographic algorithm using Paley graphs and ASCII values”, E3S Web Conf., 297 (2021), 01046, 5 pp. | DOI

[2] Beaula C., Venugopal P., Praba B., Karthik B., “Block encryption and decryption of a sentence using decomposition of the Turan graph”, J. Math., 2023, 1–8 | DOI | MR

[3] Kharari F., Teoriya grafov, Mir, M., 1973

[4] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, M., 1997 | MR

[5] Kelly P. J., “A congruence theorem for trees”, Pacific J. Math., 7 (1957), 961–968 | DOI | MR | Zbl

[6] Harary F., Palmer E., “The reconstruction of a tree from its maximal subtrees”, Canadian J. Math., 18 (1966), 803–810 | DOI | MR | Zbl

[7] Manvel B., “Reconstruction of trees”, Canadian J. Math., 22 (1970), 55–60 | DOI | MR | Zbl

[8] Abrosimov M. B., Volodina P. A., “O nekotorykh svoistvakh derevev s razmerom privedennoi kolody 1”, XIV Mezhdunar. nauch. seminar «Diskretnaya matematika i ee prilozheniya» imeni akademika O. B.-Lupanova (20–25 iyunya 2022 g., Moskva), v. 14, IPM im.-Keldysha, M., 2022, 172–174 | DOI