A340021 Number of bicolored graphs on n unlabeled nodes such that black nodes are not adjacent to each other and every white node is adjacent to a black node.

1, 1, 2, 5, 16, 66, 407, 3948, 66781, 2057140, 117820559, 12562407832, 2488441442819, 915216371901462, 625792587599236833, 797474948692631218674, 1899724021357155410243835, 8486672841492724213636009230, 71324140440429733888694354552551, 1131126439181050621704917376323373818

Offset: 0

Author

Andrew Howroyd, Dec 30 2020

Keywords

• nonn

Comments

The black nodes form a maximal independent vertex set (or a set that is both independent and dominating). For n > 0, a(n) is then the total number of indistinguishable maximal independent vertex sets summed over distinct unlabeled graphs with n nodes.

Links

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

Crossrefs

A049312 counts bicolored graphs where adjacent nodes cannot have the same color.

A000666 counts bicolored graphs where adjacent nodes can have the same color.

Cf. A339832 (independent only), A339836 (dominating only), A339837 (trees).

Programs

Mathematica

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
dom[u_, v_] := Product[2^Sum[GCD[u[[i]], v[[j]]], {j, 1, Length[v]}] - 1, {i, 1, Length[u]}];
U[nb_, nw_] := Module[{s = 0}, Do[t = 0; Do[t += permcount[v]*dom[u, v], {v, IntegerPartitions[nb]}]; s += t*permcount[u]*2^edges[u]/nb!, {u, IntegerPartitions[nw]}]; s/nw!];
a[n_] := Sum[U[k, n - k], {k, 0, n}];
Array[a, 20] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

PARI

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
dom(u, v) = {prod(i=1, #u, 2^sum(j=1, #v, gcd(u[i], v[j]))-1)}
U(nb, nw)={my(s=0); forpart(u=nw, my(t=0); forpart(v=nb, t += permcount(v) * dom(u, v)); s += t*permcount(u) * 2^edges(u)/nb!); s/nw!}
a(n)={sum(k=0, n, U(k, n-k))}