Oct 15, 2026, 5:41 PM@blinry This combination of properties seems to be what is usually just called "minimal dominating", the smallest ones are "minimum dominating".
Can you find a graph with a maximal irredundant set that is not dominating?
- Oct 15, 2026, 5:41 PM
Replies
blinryblinry@chaos.socialOct 16, 2026, 8:26 AM@tian I don't think so! Proof attempt: If S is irredundant, but not dominating, there is a node that's neither in S nor neighboring S. So we can add that node to S without making S redundant. So S was not maximal irredundant.
- Oct 16, 2026, 10:19 AM
@blinry Certainly the new node is needed for domination, but are all nodes in S needed?