OFFSET
1,7
COMMENTS
A star graph has a domination number of 1 and for n > 1 a path on n nodes has domination number floor(n/2) which is the maximum possible for a connected graph.
A minimum dominating set can be found in a tree using a greedy algorithm. First choose any node to be the root and perform a depth first search from the root. Exclude all leaves from the dominating set (except possibly the root) and also greedily exclude any other node if all children are either in the dominating set or dominated by one of their children. This method can be converted into an algorithm to compute the number of trees by domination number. See the PARI program for technical details.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..2501 (rows 1..100)
Eric Weisstein's World of Mathematics, Domination Number
Wikipedia, Dominating set
EXAMPLE
Triangle begins:
1;
1;
1;
1, 1;
1, 2;
1, 4, 1;
1, 5, 5;
1, 7, 13, 2;
1, 8, 27, 11;
1, 10, 47, 45, 3;
...
There are 3 trees with 5 nodes:
o o
| |
x---x---o o---x---o---x---o o---x---o
| |
o o
The first 2 of these have a minimum dominating set of 2 nodes and the last has a minimum dominating set of 1 node, so T(5,2)=2 and T(5,1)=1.
PROG
(PARI)
EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i ))-1, -n)}
\\ In the following, u, v, w count rooted trees weighted by domination number: u is root in set, v is root not in the set but dominatated by a child, w is root in set and not yet dominated.
T(n)={my(u=[0], v=[0], w=[1]); for(n=2, n, my(t1=EulerMT(v), t2=EulerMT(u+v)); u=y*concat([0], EulerMT(u+v+w)-t2); v=concat([0], t2-t1); w=concat([1], t1)); w*=y; my(g=x*Ser(u+v+w), gu=x*Ser(u), gw=x*Ser(w), r=Vec(g + (substvec(g, [x, y], [x^2, y^2]) - (1-1/y)*substvec(gw, [x, y], [x^2, y^2]) - g^2 + (1-1/y)*gw*(gw+2*gu) )/2)); vector(#r, n, Vecrev(r[n]/y))}
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Andrew Howroyd, Dec 19 2020
STATUS
approved