A332402 Triangle read by rows: T(n,k) is the number of simple 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

Author

Andrew Howroyd, Feb 11 2020

Keywords

• nonn
• tabl

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.

Examples

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

Links

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

Crossrefs

Row sums are A000088.

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

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

Formula

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