#mathober day 15: Irredundant
Here's a game for you: Select some nodes from this graph, so that:
1. All nodes of the graph are either in your set or neighbors of your set (your set is "dominating"), and
2. You can't remove nodes from your set without losing that property (your set is "irredundant").
How small can you make your set? How big? Can you tell why?
#mathober day 16: Isochronous Curve
There was a YouTuber called Murph
who let marbles race, and observe:
All of them, how sublime,
arrived at the same time
for the track was an isochrone curve.
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?
@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?
@blinry I choose {5, 7, 14}. That should satisfy it, and I don't think 2 nodes are possible. Since 8 is only connected to 7 either 8 or 7 needs to be in the set. Taking 8 instead of 7 "feels" wrong, 7 "gains more ground".
@envy Neat, yeah, I think 3 ist the "minimum" size. Not quite sure about the largest set yet!
@blinry I can get up to 5 I think: {1, 6, 8, 12, 14}
@LaurinMurer @envy Seems irredundant to me! Neat!
@blinry I love this
@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.