scientific article; zbMATH DE number 20509

From MaRDI portal
Publication:3979791





Let \(T\) be a tree with colors arbitrarily assigned to the vertices and edges. The subgraph of \(T\) obtained by deleting a vertex \(v\) together with all edges incident to it is called the card corresponding to vertex \(v\). A vertex of \(T\) is peripheral if it is an end of any diameter of \(T\). Let \(D_{np}(T)\) be a deck (set) of pairwise nonisomorphic cards corresponding to the peripheral vertices. Two infinite families \(A\) and \(B\) of pairs of trees are described and the following theorem is proved. Theorem 1. Let \(T_ 1\), \(T_ 2\) be a pair of colored trees with the same deck \(D_{np}(T_ 1)=D_{np}(T_ 2)\). Then one of the following holds: 1) \(T_ 1\simeq T_ 2\); 2) \(T_ 1\not\simeq T_ 2\) and the pair of trees \(T_ 1\), \(T_ 2\) belongs to one of the infinite families \(A\), \(B\). Thus all colored trees, which are not reconstructible from \(D_{np}\)-deck, are characterized. These trees are partitioned into pairs and these pairs form two infinite families.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3979791)