@blinry The first part seems simple enough, since a minimal dominating set is irredundant. To cover 8, we must pick either 7 or 8, and 7 is a better choice. Of the remaining uncovered graph, no one is sufficient, but 5 and 14 are. So, it can be made as small as three, and no smaller.
@blinry I want to start the same way for part two... The selection must include either 7 or 8 but not both, and I think it can be shown that 8 is a better choice. 7 and 8 are now simply irrelevant, and we can remove them from the graph... at which point I now want to redraw it but need to go to sleep
@blinry I hope you don't mind me dumping my unfinished thoughts into the thread. For any node to be present in an irreducible set, it has to have at least one adjacent node that witnesses its unremovability; since two nodes can't share a witness, cardinality alone bounds the size of the dominating set to at most seven members
Oct 16, 2026, 7:26 PM@chris__martin @blinry If you mean that each node in an irredundant set has a non shared witness of its nonredundancy: note that this witness can be a neighbor or the node itself, and sometimes itself is the only option.
Example (there are more trivial ones):
X—O—X
O: node
X: node that is in the irredundant set