← All problems

Spider leaf-deletion conjecture for domination-polynomial modes

5 years old · traced to

Let SS be a spider, meaning a tree with one vertex of degree greater than 22, whose legs all have length at most 33. Let S′S' be obtained from SS by deleting a leaf, and let D(S,x)D(S,x) and D(S′,x)D(S',x) be their domination polynomials. A mode of a unimodal polynomial is an index at which its coefficient sequence attains a maximum. Spider leaf-deletion conjecture. Both D(S,x)D(S,x) and D(S′,x)D(S',x) are unimodal and have modes μS\mu_S and μS′\mu_{S'}, respectively, such that

∣μS−μS′∣≤1.|\mu_S-\mu_{S'}|\leq 1.

The paper notes that this conjecture, together with its path-recursion lemma, would imply unimodality for all spider graphs. The supplied text does not establish the conjecture.

References
  1. Amanda Burcroff and Grace O'Brien, “Unimodality and monotonic portions of certain domination polynomials”, arXiv:2110.00709 (2021).

Progress summary

Refreshed
Open

No public proof or counterexample has appeared, so the conjecture remains open.

A 2021 paper formulates the conjecture for spiders whose legs have length at most three: deleting one leaf should preserve unimodality and move a mode by at most one. The paper explains that this, together with a path-recursion lemma, would imply unimodality for all spider graphs, but does not prove it.

Known results

  • All spider graphs with at most 400 legs have unimodal domination polynomials, with arbitrary leg lengths.
  • The same paper records the broader leaf-deletion question for trees as open: whether two unimodal domination polynomials can have no modes within distance one.

Current status (as of November 2026): The spider leaf-deletion conjecture remains open; the bounded result for spiders with at most 400 legs is settled, but no proof or counterexample for the stated conjecture is recorded.

Sources

Solutions 0

No solutions have been posted yet.