On the dependence polynomial of a graph
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\).
- Bounding the roots of independence polynomials.
- Clique polynomials and independent set polynomials of graphs
- Clique polynomials have a unique root of smallest modulus
- Dependence polynomials
- scientific article; zbMATH DE number 428989 (Why is no real title available?)
- Matching theory
- On the foundations of combinatorial theory I. Theory of M�bius Functions
- Julia set of some graphs using independence polynomials
- Dependence polynomials
- Dependency Pairs and Polynomial Path Orders
- Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
- scientific article; zbMATH DE number 975356 (Why is no real title available?)
- Dependence polynomials of some graph operations
This page was built for publication: On the dependence polynomial of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q854836)
