One graph shape has a higher bondage number than its degree allows.

In math, networks of dots and lines are called graphs. A dominating set is a group of dots that touches or includes every dot in the network. The bondage numberbondage numberThe minimum number of edges whose deletion increases the domination number of a graph. is the smallest count of lines you must remove to make this group need more dots. In 1998, researchers conjectured an upper limit for this number on flat, non-crossing networks, based on the highest count of lines meeting at one dot plus one. The authors tested this rule on a network shaped like a truncated octahedron. They checked every possible small group of dots and thousands of line cuts. They found this specific network breaks the rule, disproving the twenty-six-year-old conjecture.

Why it matters

This result disproves a long-standing guess in graph theory about how edges affect domination in planar graphs. It changes what mathematicians know, which influences how they study network robustness and graph properties.

Questions answered