首页 | 本学科首页   官方微博 | 高级检索  
     


Joining caterpillars and stability of the tree center
Authors:Paolo Dulio
Affiliation:a Dipartimento di Matematica, “F. Brioschi”, Politecnico di Milano, Piazza Leonardo da Vinci 32, I-20133 Milano, Italy
b Dipartimento di Matematica “U. Dini”, Univeristà di Firenze, Viale Morgagni 67/A, I-50134 Firenze, Italy
Abstract:The path-tableP(T) of a tree T collects information regarding the paths in T: for each vertex v, the row of P(T) relative to v lists the number of paths containing v of the various lengths. We call this row the path-row of v in T.Two trees having the same path-table (up to reordering the rows) are called path-congruent (or path-isomorphic).Motivated by Kelly-Ulam's Reconstruction Conjecture and its variants, we have looked for new necessary and sufficient conditions for isomorphisms between two trees.Path-congruent trees need not be isomorphic, although they are similar in some respects. In [P. Dulio, V. Pannone, Trees with path-stable center, Ars Combinatoria, LXXX (2006) 153-175] we have introduced the concepts of trunkTr(T) of a tree T and ramificationView the MathML source of a vertex vV(Tr(T)), and proved that, if the ramification of the central vertices attains its minimum or maximum value, then the path-row of a central vertex is “unique”, i.e. it is different from the path-row of any non-central vertex (in fact, this uniqueness property of a central path-row holds for all trees of diameter less than 8, regardless of the ramification values).In this paper we prove that, for all other values of the ramification, and for all diameters greater than 7, there are trees in which the above uniqueness fails.
Keywords:05C60
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号