A332402 Triangle read by rows: T(n,k) is the number of graphs on n unlabeled nodes with independent domination number k.

1, 1, 1, 2, 1, 1, 4, 5, 1, 1, 11, 16, 5, 1, 1, 34, 90, 25, 5, 1, 1, 156, 668, 188, 25, 5, 1, 1, 1044, 8648, 2394, 228, 25, 5, 1, 1, 12346, 199990, 58578, 3493, 229, 25, 5, 1, 1, 274668, 8776166, 2837118, 113197, 3758, 229, 25, 5, 1, 1

Offset

1,4

Comments

The independent domination number of a graph is the minimum size of a maximal independent set (sets which are both independent and dominating). For any graph it is greater than or equal to the domination number (A263284) and less than or equal to the independence number (A263341).

The final terms of each row tend to the sequence (1, 1, 5, 25, 229, 3759, ...). This happens because a connected graph on n nodes with n > 1 cannot have an independent domination number > floor(n/2). Similar limits are seen in A263284 and A332404 for the same reason.

Links

Table of n, a(n) for n=1..55.

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Formula

T(n,k) = T(n-1,k-1) for 2*(k-1) >= n.

Example

Triangle begins:
       1;
       1,       1;
       2,       1,       1;
       4,       5,       1,      1;
      11,      16,       5,      1,    1;
      34,      90,      25,      5,    1,   1;
     156,     668,     188,     25,    5,   1,  1;
    1044,    8648,    2394,    228,   25,   5,  1, 1;
   12346,  199990,   58578,   3493,  229,  25,  5, 1, 1;
  274668, 8776166, 2837118, 113197, 3758, 229, 25, 5, 1, 1;
  ...

Crossrefs

Row sums are A000088.

Column k=1 is A000088(n-1).

Cf. A263284, A263341, A332402, A332403, A332404, A332405.

Sequence in context: A373746 A291261 A294206 * A263284 A332404 A308905

Adjacent sequences: A332399 A332400 A332401 * A332403 A332404 A332405

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 11 2020

Status

approved