A unified approach to the first derivatives of graph polynomials (Q1805447)

The authors define a general polynomial of a graph \(G\) and prove a relation between its first derivative and the polynomials of the subgraphs of \(G\). Let \(f(\Lambda)\) be any function defined on the class of all graphs with the property \(f(\Lambda_ 1)= f(\Lambda_ 2)\) for any isomorphic \(\Lambda_ 1\) and \(\Lambda_ 2\). \(P(G, k)\) denote the sum \(\sum f(\Lambda)\) where \(\Lambda\) is any \(k\)-vertex subgraph of \(G\). The general polynomial of \(G\) is defined as \[ P(G, x)= \sum^ n_{k= 0} P(G, k) x^{n- k}. \] The main result of the paper is the equality \[ {d\over dx} P(G, x)= \sum_{v\in V(G)} P(G- v, x). \] It is shown that matching, independence, characteristic and clique polynomials are special cases of the general polynomial.