++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.

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, so each trailing 0 bit changed to a 1, provided that does not exceed the maximum N-1. At the root the children are single bit powers-of-2 up to the high bit of the maximum N-1.

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

## Order

The `order` parameter 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. 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) to (3,3).

A top-down definition is order k tree is 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, 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 an extra low 0-bit become the evens 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. arxiv:0910.4432

For order k it 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 among 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 a 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``````

## 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).

The independence number is found by starting with each leaf in an independent set and its attachment vertex not. Per the bottom-up definition this is all vertices. If N odd then the unpaired existing even vertex can be included too, for independence number ceil(N/2).

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

# HOUSE OF GRAPHS

House of Graphs entries for the trees here include

order=0, https://hog.grinvin.org/ViewGraphInfo.action?id=1310 (single vertex)
order=1, https://hog.grinvin.org/ViewGraphInfo.action?id=19655 (path-2)
order=2, https://hog.grinvin.org/ViewGraphInfo.action?id=594 (path-4)
order=3, https://hog.grinvin.org/ViewGraphInfo.action?id=700
order=5, https://hog.grinvin.org/ViewGraphInfo.action?id=21088

# OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include

``    A192021   Wiener index``