The dependence polynomial, in the dependent-set sense, of a simple graph 
is the generating polynomial for subsets
of vertices that induce at least one graph
edge:
 |
where 
is the vertex count, 
counts dependent sets of size 
, and 
is the independence
polynomial. Thus 
, 
is the edge count, and
the dependence polynomial vanishes for an empty graph.
This meaning is distinct from the signed clique
polynomial 
also called a dependence polynomial (Xie and Xu 2026).
The coefficients form a logarithmically concave sequence. Xie and Xu (2026, Theorem 2) prove that they form an ultra log-concave sequence if 
has at least one graph edge
and either has no induced 
or has an independent
vertex set of size 
.
For a graph with at least one graph edge, its dependence polynomial is real-rooted iff deleting its isolated vertices
leaves one of the following eight graphs: 
, 
, 
, 
, 
, 
, the paw graph, or the 5-vertex tree obtained by subdividing
one graph edge of 
(Xie and Xu 2026, Theorem 4). Here 
is a complete graph, 
a path graph,
a cycle graph, and 
denotes graph union.
For example, 
,
and adjoining 
isolated vertices multiplies the dependence polynomial
by 
.
