On the 5-Local Profiles of Trees

4th International Conference on Operational Research

Manik, Efron^1,2 ; Suwilo, Saib^1 ; Tulus^1 ; Sitompul, Opim Salim^3

Department of Mathematics, University of Sumatera Utara, Medan, Indonesia^1

Department of Mathematics Education, Nommensen HKBP University, Medan, Indonesia^2

Department of Information Technology, University of Sumatera Utara, Medan, Indonesia^3

关键词: Lower boundary;    Lower bounds;    Sub trees;    Y-shaped;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/300/1/012076/pdf
DOI  :  10.1088/1757-899X/300/1/012076

来源: IOP

【 摘 要 】

For T and U trees, we denote c(U, T) as the number of copies U in T, in other words: the number of homomorphism injective from U to T. The path, star, and y-shaped tree is a list of all the homomorphisms of the tree by 5-point. Furthermore, the 5-profile of the Tntree is symbolized by P, S, and Y for the paths, star, and y-shaped trees respectively. So the set limit of 5-profile, ΔT(5), is a subset of R3. Notation (p1, p2, p3) ∈ ΔT(5) corresponds to P, S, and Y respectively. (5) is a projection of ΔT(5) on the first two coordinates. Determining the area boundary of (5) is a challenging task. The d-millipede tree produces the points of (5) whose sum of p1 and p2are very small at some point. The study of whether the point generated by the d-millipede tree is the lower bound of the set (5) is a question that requires investigation. The expanded d-millipede tree is defined as the tree produced by adding sides to the leaves of the d-milipede tree. This paper discusses the coordinates of point (5) generated by the expanded d-millipede tree. The d-millipede tree is a tree with the least number of sub-trees from the family of trees with the same number of points and degrees. The d-millipede tree produces the lowest point in region (5). The points generated by the optimum tree and points generated by the expanding d-millipede tree are above the curve connecting the points generated by the d-millipede tree. So we estimate that the lower boundary region (5) is the curve connecting the points generated by the d-millipede tree.