login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A332402
Triangle read by rows: T(n,k) is the number of graphs on n unlabeled nodes with independent domination number k.
6
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
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).
Sequence in context: A373746 A291261 A294206 * A263284 A332404 A308905
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Feb 11 2020
STATUS
approved