Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika. Supplement, 2024, Issue 17, Pages 135–137
DOI: https://doi.org/10.17223/2226308X/17/34
(Mi pdma664)
 

Applied Theory of Coding, Automata and Graphs

Classification of trees whose maximal subtrees are all isomorphic

M. B. Abrosimov, D. A. Tomilov

Saratov State University
References:
Abstract: 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.
Document Type: Article
UDC: 519.17
Language: Russian
Citation: M. B. Abrosimov, D. A. Tomilov, “Classification of trees whose maximal subtrees are all isomorphic”, Prikl. Diskr. Mat. Suppl., 2024, no. 17, 135–137
Citation in format AMSBIB
\Bibitem{AbrTom24}
\by M.~B.~Abrosimov, D.~A.~Tomilov
\paper Classification of trees whose maximal subtrees are all isomorphic
\jour Prikl. Diskr. Mat. Suppl.
\yr 2024
\issue 17
\pages 135--137
\mathnet{http://mi.mathnet.ru/pdma664}
\crossref{https://doi.org/10.17223/2226308X/17/34}
Linking options:
  • https://www.mathnet.ru/eng/pdma664
  • https://www.mathnet.ru/eng/pdma/y2024/i17/p135
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Prikladnaya Diskretnaya Matematika. Supplement
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025