Login
You're viewing the discuss.systems public feed.

Replies

  • blinryblinry@chaos.social
    Oct 15, 2026, 4:18 PM

    #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?

    #mathober2026 #math #graphtheory

    A connected graph of 15 nodes.
    💬 5🔄 4⭐ 0
  • blinryblinry@chaos.social
    Oct 16, 2026, 1:16 PM

    #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.

    #mathober2026 #math

    💬 2🔄 2⭐ 0
  • 💬 3🔄 0⭐ 0
  • 💬 1🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • Tiantian@kif.rocks
    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?

    💬 1🔄 0⭐ 0
  • blinryblinry@chaos.social
    Oct 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.

    💬 1🔄 0⭐ 0
  • Tiantian@kif.rocks
    Oct 16, 2026, 10:19 AM

    @blinry Certainly the new node is needed for domination, but are all nodes in S needed?

    💬 0🔄 0⭐ 0
  • Nicoenvy@noot.noot.cloud
    Oct 15, 2026, 6:54 PM

    @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".

    💬 1🔄 0⭐ 0
  • blinryblinry@chaos.social
    Oct 15, 2026, 7:46 PM

    @envy Neat, yeah, I think 3 ist the "minimum" size. Not quite sure about the largest set yet!

    💬 1🔄 0⭐ 0
  • 💬 1🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • Chris Martinchris__martin@functional.cafe
    Oct 16, 2026, 5:59 AM

    @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.

    💬 1🔄 0⭐ 0
  • Chris Martinchris__martin@functional.cafe
    Oct 16, 2026, 6:27 AM

    @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

    💬 1🔄 0⭐ 0
  • Chris Martinchris__martin@functional.cafe
    Oct 16, 2026, 5:17 PM

    @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

    💬 1🔄 0⭐ 0
  • Tiantian@kif.rocks
    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

    💬 1🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 1