𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Numbering binary trees with labeled terminal vertices

✍ Scribed by F. James Rohlf

Publisher
Springer
Year
1983
Tongue
English
Weight
353 KB
Volume
45
Category
Article
ISSN
1522-9602

No coin nor oath required. For personal study only.

✦ Synopsis

For each rooted binary tree with t labeled terminal vertices (leaves) a natural number can be assigned uniquely. Unrooted trees with t labeled terminal vertices and t-2 unlabeled internal vertices of degree 3 can also be numbered uniquely using the same convention. Rooted trees in which the heights of the internal vertices are rank ordered are also considered. Applications to problems in taxonomy are discussed.

πŸ“œ SIMILAR VOLUMES

On labeled vertex-transitive digraphs wi
On labeled vertex-transitive digraphs with a prime number of vertices
✍ Chong-Yun Chao; Jacqueline G. Wells πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 481 KB

## We enumerate, up to isomorphism, several classes of labeled vertex-transitive digraphs with a prime number of vertices. There are many unsolvedi enumeration problems stated in [S]. Recently, Robinson in [8] posed more enumeration problems. Here, we give some partial answer to the problems posed

A lower bound on the number of spanning
A lower bound on the number of spanning trees with k end-vertices
✍ Katherine Heinrich; Guizhen Liu πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 286 KB πŸ‘ 1 views

If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span

The ally-reconstruction number of a tree
The ally-reconstruction number of a tree with five or more vertices is three
✍ Wendy Myrvold πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 788 KB

## Abstract The __ally‐reconstruction number__ of a graph __G__, ally‐rn(__G__), is the minimum number of vertex‐deleted subgraphs required in order to identify __G__ up to isomorphism. In this paper, we show that ally‐rn(__T__) = 3 for any tree __T__ with five or more vertices.

A spanning tree of the 2m-dimensional hy
A spanning tree of the 2m-dimensional hypercube with maximum number of degree-preserving vertices
✍ Sul-young Choi; Puhua Guan πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 190 KB

For an n-dimensional hypercube Q., the maximum number of degree-preserving vertices in a spanning tree is 2"jn if n = 2" for an integer M. (If n # 2", then the maximum number of degree-preserving vertices in a spanning tree is less than 2"/n.) We also construct a spanning tree of Qzm with maximum nu