DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

J.-L. Shang

Title:

Branch-weight unique trees

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-10-09, Revised: 2019-11-15, Accepted: 2019-11-15, 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

PDF
Close