Iterated Joining of Rooted Trees

作者：Dulio Paolo^*; Pannone Virgilio

来源：Graphs and Combinatorics, 2013, 29(5): 1287-1304.

DOI：10.1007/s00373-012-1178-7

• Caterpillar
• Center
• Generating function
• Joining
• Path
• Path-congruence
• Tree

For a given pair of trees T (1), T (2), two vertices and are said to be path-congruent if, for any integer k a parts per thousand yen 1, the number p (k) (v (1)) of paths contained in T (1), of length k and passing through v (1), equals the number p (k) (v (2)) of paths contained in T (2), of length k and passing through v (2). We first provide polynomial constructions, and related examples, of pairs of non-isomorphic rooted trees with path-congruent roots v (1), v (2). Then we employ a joining operation between to get a tree J (2) where v (1), v (2) do not necessarily belong to a maximal path. For any integer number m, the joining can be made such that the set {v (1), v (2)} has distance m from the center Z(J (2)) of J (2). By iterating the idea, an s-fold joining J (s) can be considered, where the roots v (1), . . . , v (s) , s a parts per thousand yen 2, are consecutive vertices of J (s) . For s = 3 we give an explicit general construction where . On the other hand we prove that for all s %26gt; 2, if and are isomorphic.

• 出版日期2013-9