Login
You're viewing the scl.zmb.cm 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🔄 0⭐ 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

    💬 0🔄 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.

    💬 0🔄 0⭐ 0