On the dependence polynomial of a graph (Q854836)

For an \(n\)-vertex graph \(G\) and \(i=0, 1, \dots, n\), let \(c_i\) denote the number of complete subgraphs on \(i\) vertices in \(G\). The dependence polynomial \(P_G(z)\) of \(G\) is defined by \(P_G(z)=1+\sum_{i=1}^n (-1)^i c_iz^i\). Using a Möbius-type inversion formula, the authors show that \[ \begin{aligned} P_G(z)&=\sum_{\emptyset\not=\mathcal{W}\subseteq\mathcal{V}} (-1)^{| \mathcal{W}| -1}(1-z)^{| \bigcap\mathcal{W}| }\\ &=\sum_{k=1}^m (-1)^{k-1} \sum_{1\leq i_1 <\cdots < i_k\leq m} (1-z)^{| V_{i_1}\cap\cdots\cap V_{i_k}| },\end{aligned} \] where \(\mathcal{V}=\{V_1, \dots, V_m\}\) denotes the set of (distinct) maximal complete subgraphs of \(G\). For the line graph \(L(G)\) of \(G=(V,E)\), this reads as follows: \(P_{L(G)}(z)=\sum_{v\in V}(1-z)^{d(v)} - tz^3+ez+1-n\), where \(n=| V| \), \(e=| E| \), \(t\) denotes the number of triangles in \(G\), and \(d(v)\) is the degree of \(v\) in \(G\). The authors also discuss the relation of the dependence polynomial of the complement of the line graph of \(G\) to the matching polynomial of \(G\).