A339829 -id:A339829 - cp's OEIS frontend

A339830 Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other.

1, 2, 2, 4, 10, 26, 75, 234, 768, 2647, 9466, 34818, 131149, 503640, 1965552, 7777081, 31138051, 125961762, 514189976, 2115922969, 8769932062, 36584593158, 153510347137, 647564907923, 2744951303121, 11687358605310, 49965976656637, 214423520420723, 923399052307921

Offset: 0

Andrew Howroyd, Dec 19 2020

nonn

The black nodes form an independent vertex set. For n > 0, a(n) is then the total number of indistinguishable independent vertex sets summed over distinct unlabeled trees with n nodes.

			a(2) = 2 because at most one node can be colored black.
a(3) = 4 because the only tree is the path graph P_3. If the center node is colored black then neither of the ends can be colored black; otherwise zero, one or both of the ends can be colored black. In total there are 4 possibilities.
There are 3 trees with 5 nodes:
    o                                     o
    |                                     |
    o---o---o    o---o---o---o---o    o---o---o
    |                                     |
    o                                     o
These correspond respectively to 11, 9 and 6 bicolored trees (with black nodes not adjacent), so a(5) = 11 + 9 + 6 = 26.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Eric Weisstein's World of Mathematics, Independent Vertex Set

Cf. A038056 (bicolored trees), A339829, A339831, A339832, A339834, A339837.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=v=[1]); for(n=2, n, my(t=concat([1], EulerT(v))); v=concat([1], EulerT(u+v)); u=t); my(g=x*Ser(u+v), gu=x*Ser(u)); Vec(1 + g + (subst(g,x,x^2) - subst(gu,x,x^2) - g^2 + gu^2)/2)}

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

Original entry on oeis.org

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, 124, 27, 1, 13, 103, 287, 141, 6, 1, 14, 140, 553, 528, 65, 1, 16, 182, 966, 1537, 446, 11, 1, 17, 230, 1538, 3712, 2080, 163, 1, 19, 284, 2323, 7788, 7516, 1366, 23

Offset: 1

Andrew Howroyd, Dec 19 2020

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.

			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.

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

Row sums are A000055.

Cf. A065033, A332401 (connected graphs), A339829 (independence number), A339834, A339835.

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))}

cp's OEIS Frontend

A339830 Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI