Classification of trees whose maximal subtrees are all isomorphic

M. B. Abrosimov ; D. A. Tomilov

Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 135-137

Résumé

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.

Détail

Keywords: graph, tree, reconstructibility.