The Covered Components Polynomial: A New Representation of the Edge Elimination Polynomial

Abstract

Motivated by the definition of the edge elimination polynomial of a graph we define the covered components polynomial counting spanning subgraphs with respect to their number of components, edges and covered components. We prove a recurrence relation, which shows that both graph polynomials are substitution instances of each other. We give some properties of the covered components polynomial and some results concerning relations to other graph polynomials.