Article in volume
Authors:
Title:
Branch-weight unique trees
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 405-416
Received: 2017-10-09 , Revised: 2019-11-15 , Accepted: 2019-11-15 , Available online: 2019-12-13 , https://doi.org/10.7151/dmgt.2264
Abstract:
A branch at a vertex $x$ in a tree is a maximal subtree containing $x$ as an
endvertex. The branch-weight of $x$ is the maximum number of edges in any
branch at $x$. The branch-weight sequence of a tree is the multiset consisting
of the branch-weights of all vertices arranged in nonincreasing order.
Non-isomorphic trees may have the same branch-weight sequence. A tree $T$ is
said to be branch-weight unique in a family of trees if $T$ is uniquely
determined in the family by its branch-weight sequence. A spider is a tree in
which exactly one vertex has degree exceeding two. It is known that spiders are
branch-weight unique in the family of spiders but not in the family of all trees.
In this study, a necessary and sufficient condition is obtained whereby a spider
may be branch-weight unique in the family of all trees. Moreover, two types of
trees are proposed to be branch-weight unique in the family of all trees.
Keywords:
branch-weight, branch-weight sequence, branch-weight unique, tree, spider
References:
- C.A. Barefoot, R.C. Entringer and L.A. Székely, Extremal values for ratios of distances in trees, Discrete Appl. Math. 80 (1997) 37–56.
https://doi.org/10.1016/S0166-218X(97)00068-1 - F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley Pub. Co., Redwood City, 1990).
- C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869) 185–190.
https://doi.org/10.1515/crll.1869.70.185 - C. Lin and J.-L. Shang, Statuses and branch-weights of weighted trees, Czechoslovak Math. J. 59 (2009) 1019–1025.
https://doi.org/10.1007/s10587-009-0071-x - W. Piotrowski, A generalization of branch weight centroids, Appl. Math. (Warsaw) 19 (1987) 541–545.
https://doi.org/10.4064/am-19-3-4-541-545 - W. Piotrowski and M.M. Sysło, Some properties of graph centroids, Ann. Oper. Res. 33 (1991) 227–236.
https://doi.org/10.1007/BF02115757 - J.-L. Shang and C. Lin, An uniqueness result for the branch-weight sequences of spiders, The WHAMPOA–-An Interdisciplinary Journal 54 (2008) 31–38.
- R. Skurnick, Integer Sequences Associated with Trees, Ph.D. Dissertation (City University of New York, 1994).
- R. Skurnick, Extending the concept of branch-weight centroid number to the vertices of all connected graphs via the Slater number, Graph Theory Notes N.Y. 33 (1997) 28–32.
- R. Skurnick, A characterization of the centroid sequence of a caterpillar, Graph Theory Notes N.Y. 41 (2001) 7–13.
- P.J. Slater, Accretion centers: A generalization of branch weight centroids, Discrete Appl. Math. 3 (1981) 187–192.
https://doi.org/10.1016/0166-218X(81)90015-9
Close