Conjectures on status sequences and branch-weight sequences of trees

Jen-Ling Shang

Department of Banking and Finance

Kainan University

jlshang@mail.knu.edu.tw

    The status [1, 2, 3, 4, 5] of a vertex in a graph is the sum of the distances between the vertex and each vertex in the graph. The status sequence [1, 2, 3, 4, 5] of a graph is the list of the statuses of all vertices arranged in nondecreasing order. A graph is called status injective [1, 2, 3, 4, 5] if the status sequence consists of distinct numbers. A tree is called weakly status injective [5] if any two vertices of the tree having the same status are endvertices. A tree `T` is said to be status unique [3, 5] in the family of all trees if whenever `T'` is a tree with the same status sequence as `T`, then `T'` and `T` are isomorphic. Recently [5] shows that a weakly status injective tree is status unique in the family of all trees. We have the following conjecture.
Conjugate 1: A tree in which all non-endvertices having distinct statuses is status unique in the family of all trees.
A branch [6, 7, 8, 9] at a vertex `b` in a tree is a maximal subtree containing `b` as an endvertex. Let `B_1,B_2,ldots,B_m` `(M\geq 1)` be several distinct branches at `b` in the tree. Assume that `U` is the subtree induced by `V(B_1)\cup V(B_2)\cup\cdots\cup V(B_m)`. Then `U` is called a union branch [5] at `b`. The branch-weight [6, 7, 8, 9] of `b` is the maximum number of edges in any branch at `b`. The branch-weight sequence [6, 7, 8] of a tree is the list of the branch-weights of all vertices arranged in nonincreasing order. Let `T` be a tree and `x,y` be a pair of distinct non-endvertices in `T` with the same status. Suppose that `A` is a union branch at `x` and `B` is a union branch at `y`, where `V(A)\cap V(B)=\phi` and `|V(A)|=|V(B)|`. Let `C` be the subgraph of `T` induced by the vertex set `(V(T)-(V(A)\cup V(B)))\cup\{x,y\}`. Let `T'` be the tree constructed from `A`, `B`, and `C` by identifying the vertex `x` in `A` with the vertex `y` in `C`, and identifying the vertex `y` in `B` with the vertex `x` in `C`. It is shown that `T'` and `T` have the same status sequence [4]. We call such a tree `T'` a status-retained transfer of T. We now propose the following conjectures.
Conjugate 2: Assume that `T_0` is a tree and there is at least a pair of distinct non-endvertices of `T_0` with the same status. Let `T` be a tree. Then, `T` has the same status sequence as `T_0` if and only if there exist trees `T_1,T_2,ldots,T_k` `(k\in\mathbb{N})` such that `T_i` is a status-retained transfer of `T_{i-1}` for `i=1,2,ldots,k` and `T_k~= T`.
Conjugate 3: Two trees have the same branch-weight sequence if they have the same status sequence.
Remark: Supported by the Ministry of Science and Technology of R.O.C. under grants MOST 105-2115-M-424-001, MOST 106-2115-M-424-001.

Keyword: status, status sequence, branch-weight, branch-weight sequence, tree