PUB - Publikationen an der Universität Bielefeld

The dependence polynomial P-G = P-G (z) of a graph G is defined by P-G (z) := Sigma(n)(i)(=0)(-1)(i)c(i)z(i) where c(i) = c(i) (G) is the number of complete subgraphs of G of cardinality i. It is clear that the complete subgraphs of G form a poset relative to subset inclusion. Using Mobius inversion, this yields various identities involving dependence polynomials implying in particular that the dependence polynomial of the line graph L(G) of G is determined uniquely by the (multiset of) vertex degrees of G and the number of triangles in G. Furthermore, the dependence polynomial of the complement of the line graph of G is closely related to the matching polynomial of G, one of the most 'prominent' polynomials studied in graph theory. (c) 2005 Elsevier Ltd. All rights reserved.