New Perspectives on the Unimodality of Domination Polynomials
Mohamed Omar · 2026
Read New Perspectives on the Unimodality of Domination Polynomials by Mohamed Omar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-14494.txt.
Introduction
Mohamed Omar studies a counting polynomial in this 2026 math paper. The domination polynomial of a graph counts its dominating sets by size. A dominating set is a set of vertices such that every vertex is in the set or next to one in it. The polynomial's coefficients record how many dominating sets have each size.
The open question is unimodality: do those counts rise, peak once, then fall? Omar brings new perspectives to that question. The abstract gives the definition in full formal terms. Readers get fresh angles on a clean graph theory problem, where a simple shape claim about a sequence of counts has resisted full proof.
Catalog record
| CREATOR | Mohamed Omar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-14494
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New Perspectives on the Unimodality of Domination Polynomials Mohamed Omar Abstract . The domination polynomial of a graph G G is given by D ( G , x ) = ∑ k = 0 n d k ( G ) x k D(G,x)=\sum_{k=0}^{n}d_{k}(G)x^{k} where d k ( G ) d_{k}(G) records the number of k k -element dominating sets in G G . A conjecture of Alikhani and Peng asserts that these polynomials have unimodal coefficient sequences. We develop three complementary perspectives that strengthen existing tools for resolving the conjecture. First, we view dominating sets as transversals of the closed neighborhood hypergraph. Motivated by the relationship between the unimodality of a polynomial and its roots, we use this perspective to expand on known root phenomena for domination polynomials. In particular, we obtain a bound on the modulus of domination roots that is linear in the maximum degree of a graph, improving related exponential bounds of Bencs, Csikvári and Regts. The hypergraph viewpoint also yields explicit combinatorial formulas for top coefficients of D ( G , x ) D(G,x) , extending formulas in the literature and offering fruitful ground for combinatorial approaches to the unimodality conjecture. Second, we strengthen the coefficient-ratio method of Beaton and Brown. This includes tightening their inequalities, and combining a union bound for non-dominating k k -element sets with an overlap correction based on spanning trees. This produces a new parameter τ k ( G ) \tau_{k}(G) measuring maximal pairwise neighborhood overlap and yields an overlap-corrected sufficient criterion for unimodality. Third, we prove that the domination polynomial of threshold graphs are log-concave, and hence unimodal, by a planar network argument from total positivity. This offers a new tactic for resolving the unimodality of hereditary graph classes. 2020 Mathematics Subject Classification 05C31, 05C69 1. Introduction Let G be a finite simple undirected graph with vertex set V(G) , and n=|V(G)| . A set S\subseteq V(G) is dominating if every vertex is either in S or adjacent to a vertex of S . Let d_{k}(G) denote the number of dominating sets of size k . Alikhani and Peng [ 1 ] introduced the domination polynomial given by (1.1) D(G,x)=\sum_{k=0}^{n}d_{k}(G)x^{k}, which records dominating sets of varying sizes in its coefficients. Domination polynomials have since been studied from several points of view, including recurrence relations and splitting formulas [ 13 ] , domination equivalence and reconstruction questions [ 4 ] , and the distribution of roots [ 2 , 3 , 6 ] . The domination polynomial packages dominating set information in a way that parallels several other graph polynomials. The independence polynomial counts independent sets by size, while the domination polynomial counts hitting sets for closed neighborhoods. Matching polynomials and independence polynomials often exhibit strong analytic phenomena (real-rootedness, log-concavity, sharp zero-free regions) that can be leveraged for coefficient questions. Domination polynomials are less rigid, but their coefficient sequences still appear to have robust shape. One reason is that dominating sets form a large and highly correlated family: in most graphs, once a set is moderately large, it is likely to dominate many vertices simultaneously. The normalized coefficients r_{k}(G) from ( 1.2 ) make this probabilistic intuition precise. Another source of structure comes from graph operations. For disjoint unions one has D(G_{1}\cup G_{2},x)=D(G_{1},x)\,D(G_{2},x) , and for joins there are similar explicit formulas, see [ 13 ] . Such identities allow one to build large families of graphs with controllable domination polynomials from smaller pieces. However, unimodality is not automatically preserved under all natural operations, and controlling the interaction between pieces remains delicate. This is one reason it is helpful to have several complementary approaches to the unimodality conjecture of Alikhani and Peng [ 1 ] , which is one of the long standing conjectures on these polynomials. Conjecture 1 ( [ 1 ] ) . For every finite graph G , the domination sequence (d_{k}(G))_{k=0}^{n} is unimodal. In many settings unimodality is a shadow of a stronger property such as log-concavity or real-rootedness, but domination polynomials do not generally enjoy either: even when G is a tree, domination polynomials can have nonreal roots and need not be log-concave [ 2 ] . Existing proofs of unimodality therefore tend to rely on more delicate combinatorial or probabilistic structure, and even basic families such as trees remain challenging. The current evidence for Conjecture 1 comes from several directions. First, the conjecture holds for a number of dense families where domination is “easy” in the sense that a random set of size about n/2 almost surely dominates. This includes graphs of sufficiently large minimum degree [ 2 ] . Second, the conjecture has been verified for certain highly structured graph classes, including complete multipartite graphs [ 2 ] and other families with explicit domination recurrences. It has also been verified for many special families of trees, graphs with maximum degree at most 400 , and persists on other highly specialized families (see [ 8 ] ). On the other hand, sparse graphs are genuinely subtle. For example, for trees the domination number can be linear in n , and the family of dominating sets reflects fine local structure (leaves, supports, and branching). From this point of view, Conjecture 1 for trees is reminiscent of the long-standing conjecture that the independence polynomial of a tree is unimodal. In both cases, the central coefficients are governed by many competing local configurations. It is therefore natural to look for methods that are sensitive to local neighborhood structure but still yield global control. The three perspectives developed here aim to do exactly that: Perspective 1 translates domination into a hypergraph independence problem and imports global analytic information. Perspective 2 measures the failure of domination by local avoidance events but corrects for their overlaps. Perspective 3 imports theory from total positivity to establish log-concavity and hence unimodality. Before detailing the results from each perspective, we detail pertinent relevant results in the literature. One of the most general results to date is due to Beaton and Brown [ 2 ] . They introduced the normalized coefficients (1.2) r_{k}(G):=\frac{d_{k}(G)}{\binom{n}{k}}, interpretable as the probability that a uniformly random k -element subset of V(G) is dominating. They proved that r_{k}(G) is nondecreasing in k . Since \binom{n}{k} is increasing for k\leq\lfloor n/2\rfloor , this implies that d_{k}(G) is increasing for k\leq\lfloor n/2\rfloor . The same paper provides a criterion that forces the tail of the domination sequence to be nonincreasing. In one convenient form, if k\geq n/2 and r_{k}(G)\ \geq\frac{n-k}{k+1} , then d_{k}(G)\geq d_{k+1}(G)\geq\cdots\geq d_{n}(G) . Together with the monotonicity of r_{k}(G) , it follows that verifying this inequality at k=\lceil n/2\rceil implies unimodality with mode \lceil n/2\rceil . A different but closely related line of work concerns the roots of domination polynomials. Since D(G,x) has nonnegative coefficients it has no positive real roots, but it can have complex roots with positive real part and with arguments close to 0 . On the real axis, the picture is now essentially complete: Beaton and Brown proved that the closure of the set of real domination roots is (-\infty,0] [ 3 ] . For complex roots, Bencs, Csikvári, and Regts used Wagner’s weighted subgraph counting polynomial to obtain a