The h-vector of coned graphs

Abstract

The coned graph Ĝ on a finite graph G is obtained by joining each vertex of G to a new vertex p with a simple edge. In this work we show a combinatorial interpretation of each term in the h-vector of Ĝ in terms of partially edge-rooted forests in the base graph G. In particular, our interpretation does not require edge ordering. For an application, we will derive an exponential generating function for the sequence of h-polynomials for the complete graphs. We will also give a new proof for the number of spanning trees of the wheels. © 2010 Elsevier Ltd. All rights reserved.