A332402 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

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;

2, 1, 1;

4, 5, 1, 1;

11, 16, 5, 1, 1;

34, 90, 25, 5, 1, 1;