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 N1.
The parent of vertex n is that n with its lowest 1bit 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 N1. At the root the children are single bit powersof2 up to the high bit of the maximum N1.
__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 topdown definition is order k tree is two copies of k1, one at the root and the other a child of that root. In the N=8 order=3 example above, 03 is an order=2 and 47 is another, with 4 starting as a child of the root 0.
A bottomup definition is order k tree as order k1 with a new leaf vertex added to each existing vertex. The vertices of k1 with an extra low 0bit become the evens of k. An extra low 1bit 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
orGraph>new()
.N
is the number of vertices, 0 to N1. Or insteadorder
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. Optionundirected => 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
(k1)*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) =  = k1 +  for k>=1
binomial(2^k, 2) 2^k  1
The tree for k>=1 has diameter 2*k1 between ends of the deepest and seconddeepest 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^k1)
> 1/2 as k>infinity
Independence and Domination
From the bottomup 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 nearperfect 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 bottomup 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 (path2)
 order=2, https://hog.grinvin.org/ViewGraphInfo.action?id=594 (path4)
 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
http://oeis.org/A192021 (etc)
A192021 Wiener index
SEE ALSO
Graph::Maker, Graph::Maker::BalancedTree
LICENSE
Copyright 2015, 2016, 2017 Kevin Ryde
This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.