DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

J.-L. Shang

Jen-Ling Shang

Department of Banking and Finance
Kainan University
Luzhu, Taoyuan 33857, Taiwan, ROC

email: jlshang@mail.knu.edu.tw

Title:

Branch-weight unique trees

PDF

Source:

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:

  1. 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
  2. F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley Pub. Co., Redwood City, 1990).
  3. C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869) 185–190.
    https://doi.org/10.1515/crll.1869.70.185
  4. 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
  5. 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
  6. 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
  7. 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.
  8. R. Skurnick, Integer Sequences Associated with Trees, Ph.D. Dissertation (City University of New York, 1994).
  9. 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.
  10. R. Skurnick, A characterization of the centroid sequence of a caterpillar, Graph Theory Notes N.Y. 41 (2001) 7–13.
  11. 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