cp's OEIS Frontend

A339833 Irregular triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with domination number k, n >= 1, 1 <= k <= A065033(n+1).

%I A339833 #13 Feb 16 2025 08:34:01
%S A339833 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,1,11,72,
%T A339833 124,27,1,13,103,287,141,6,1,14,140,553,528,65,1,16,182,966,1537,446,
%U A339833 11,1,17,230,1538,3712,2080,163,1,19,284,2323,7788,7516,1366,23
%N A339833 Irregular triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with domination number k, n >= 1, 1 <= k <= A065033(n+1).
%C A339833 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.
%C A339833 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.
%H A339833 Andrew Howroyd, <a href="/A339833/b339833.txt">Table of n, a(n) for n = 1..2501</a> (rows 1..100)
%H A339833 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominationNumber.html">Domination Number</a>
%H A339833 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dominating_set">Dominating set</a>
%e A339833 Triangle begins:
%e A339833   1;
%e A339833   1;
%e A339833   1;
%e A339833   1,  1;
%e A339833   1,  2;
%e A339833   1,  4,  1;
%e A339833   1,  5,  5;
%e A339833   1,  7, 13,  2;
%e A339833   1,  8, 27, 11;
%e A339833   1, 10, 47, 45, 3;
%e A339833   ...
%e A339833 There are 3 trees with 5 nodes:
%e A339833     o                                     o
%e A339833     |                                     |
%e A339833     x---x---o    o---x---o---x---o    o---x---o
%e A339833     |                                     |
%e A339833     o                                     o
%e A339833 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.
%o A339833 (PARI)
%o A339833 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)}
%o A339833 \\ 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.
%o A339833 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))}
%Y A339833 Row sums are A000055.
%Y A339833 Cf. A065033, A332401 (connected graphs), A339829 (independence number), A339834, A339835.
%K A339833 nonn,tabf
%O A339833 1,7
%A A339833 _Andrew Howroyd_, Dec 19 2020