++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# NAME

Graph::Maker::BinomialTree - create binomial tree graph

# SYNOPSIS

`````` use Graph::Maker::BinomialTree;
\$graph = Graph::Maker->new ('binomial_tree', N => 32);``````

# DESCRIPTION

`Graph::Maker::BinomialTree` creates a `Graph.pm` graph of a binomial tree with N vertices. Vertices are numbered from 0 at the root through to N-1.

``````          __0___
/  |   \        N => 8
1   2    4
|   / \
3  5   6
|
7``````

The parent of vertex n is that n with its lowest 1-bit cleared to 0. Conversely, the children of a vertex n=xx1000 are xx1001, xx1010, xx1100, each low 0 bit changed to a 1, provided doing so does not exceed the maximum vertex number N-1. At the root, the children are single bit powers 2^p up to high bit of the limit N-1.

By construction, the tree is labelled in pre-order since a vertex xx1000 has below it all xx1yyy.

## Order

Option `order => k` is another way to specify the number of vertices. A tree of order k has N=2^k many vertices. Such a tree has depth levels 0 to k inclusive. The number of vertices at depth d is the binomial coefficient binom(k,d), hence the name of the tree.

The N=8 example above is order=3 and the number of vertices at each depth is 1,3,3,1 which are binomials (3,0) through (3,3).

A top-down definition is order k tree as two copies of k-1, one at the root and the other a child of that root. In the N=8 order=3 example above, 0-3 is an order=2 and 4-7 is another order=2, with 4 starting as a child of the root 0.

A bottom-up definition is order k tree as order k-1 with a new leaf vertex added to each existing vertex. The vertices of k-1 with extra low 0-bit become the even vertices of k. An extra low 1-bit is the new leaves.

Binomial tree order=5 appears on the cover of Knuth "The Art of Computer Programming", volume 1, "Fundamental Algorithms", second edition.

# FUNCTIONS

`\$graph = Graph::Maker->new('binomial_tree', key => value, ...)`

The key/value parameters are

``````    N           =>  integer
order       =>  integer
graph_maker => subr(key=>value) constructor, default Graph->new``````

Other parameters are passed to the constructor, either `graph_maker` or `Graph->new()`.

`N` is the number of vertices, 0 to N-1. Or instead `order` gives N=2^order many vertices.

Like `Graph::Maker::BalancedTree`, if the graph is directed (the default) then edges are added both up and down between each parent and child. Option `undirected => 1` creates an undirected graph and for it there is a single edge from parent to child.

# FORMULAS

## Wiener Index

The Wiener index of the binomial tree is calculated in

K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, "Wiener index of Binomial Trees and Fibonacci Trees", Intl J Math Engg with Comp, 2009, https://arxiv.org/abs/0910.4432

Order k is

``````                (k-1)*4^k + 2^k
Wiener(k) = ---------------  = 0, 1, 10, 68, 392, ... (A192021)
2``````

The Wiener index is total distance between pairs of vertices, so the mean distance is, with binomial to choose 2 of the 2^k vertices,

``````                     Wiener(k)                k
MeanDist(k) = ---------------- =  k-1 + -------      for k>=1
binomial(2^k, 2)          2^k - 1``````

The tree for k>=1 has diameter 2*k-1 between ends of the deepest and second-deepest subtrees of the root. The mean distance as fraction of the diameter is then

``````    MeanDist(k)    1       1              1
----------- = --- - ------- + -------------------
diameter(k)    2    4*k - 4   (2 - 1/k) * (2^k-1)

-> 1/2  as k->infinity``````

## Balanced Binary

An ordered tree can be coded as pre-order balanced binary by writing at each vertex

``    1,  balanced binaries of children,  0``

The bottom-up definition above is a new leaf as new first child of each vertex. That means the initial 1 becomes 110, so starting 10 for single vertex get repeated substitutions

``    10, 1100, 11011000, ...   (A210995)``

The top-down definition above is a copy of the tree as new last child, so one copy at *2 and one at *2^2^k, giving

``````    k-1:   1, tree k-1, 0
k:     1, tree k-1, 1, tree k-1, 0, 0

b(k) = (2^(2^k)+2) * b(k-1), starting b(0)=2
= 2*prod(i=1,k, 2^(2^i)+2)
= 2, 12, 216, 55728, 3652301664, ...  (A092124)``````

The tree is already labelled in pre-order so balanced binary follows from the parent rule. The balanced binary coding is 1 at a vertex and later 0 when pre-order skips up past it. A vertex with L many low 1-bits skips up past L many (including itself).

``    vertex n:  1, 0 x L     where L=CountLowOnes(n)``

The last L goes up only to the depth of the next vertex. The balance can be completed by extending to total length 2N for N vertices. The tree continued infinitely is

``````    1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, ...   (A079559)
^  ^     ^  ^        ^  ^     ^  ^
0  1     2  3        4  5     6  7``````

## Independence and Domination

From the bottom-up definition above, a tree of even N has a perfect matching, being each odd n which is a leaf and its even attachment. An odd N has a near-perfect matching (one vertex left over).

Like all trees with a perfect matching, the independence number is then half the vertices, and when N odd can include the unpaired and work outwards from there by matched pairs so indnum = ceil(N/2).

The domination number is found by starting each leaf not in the dominating set and its attachment vertex in the set. This is all vertices so domnum = floor(N/2) except N=1 domination number 1.

# HOUSE OF GRAPHS

House of Graphs entries for the trees here include

n=1 (order=0), https://hog.grinvin.org/ViewGraphInfo.action?id=1310 single vertex
n=2 (order=1), https://hog.grinvin.org/ViewGraphInfo.action?id=19655 path-2
n=4 (order=2), https://hog.grinvin.org/ViewGraphInfo.action?id=594 path-4
n=5 https://hog.grinvin.org/ViewGraphInfo.action?id=30 fork
n=6 https://hog.grinvin.org/ViewGraphInfo.action?id=496 E graph
n=7 https://hog.grinvin.org/ViewGraphInfo.action?id=714
n=8 (order=3), https://hog.grinvin.org/ViewGraphInfo.action?id=700
n=16 (order=4), https://hog.grinvin.org/ViewGraphInfo.action?id=28507
n=32 (order=5), https://hog.grinvin.org/ViewGraphInfo.action?id=21088
n=64 (order=6), https://hog.grinvin.org/ViewGraphInfo.action?id=33543
n=128 (order=6), https://hog.grinvin.org/ViewGraphInfo.action?id=33545

# OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to the binomial tree include

``````    A192021   Wiener index
A092124   pre-order balanced binary coding, decimal
A210995     binary
A079559     binary sequence of 0s and 1s``````