No label defined (Q3979791)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 20509
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 20509 |
Statements
26 June 1992
0 references
reconstruction
0 references
colored trees
0 references
0 references
0.8728603
0 references
0.8632165
0 references
0.85948986
0 references
0 references
0 references
0 references
0 references
0.8494867
0 references
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.
0 references