scientific article; zbMATH DE number 20509
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.
- Reconstruction for Colorings on Trees
- Recoloring graphs via tree decompositions
- Note on the reconstruction of vertex colored graphs
- An extended formulation of the convex recoloring problem on a tree
- Building graphs from colored trees
- Reconfiguring vertex colourings of 2-trees
- scientific article; zbMATH DE number 4035877
- Multicolored trees in complete graphs
- Multicolored trees in complete graphs
- On generating series of coloured planar trees
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)