About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
European Journal of Combinatorics
Paper
The enumeration of vertex induced subgraphs with respect to the number of components
Abstract
Inspired by the study of community structure in connection networks, we introduce the graph polynomial Q(G;x,y), the bivariate generating function which counts the number of connected components in induced subgraphs. We give a recursive definition of Q(G;x,y) using vertex deletion, vertex contraction and deletion of a vertex together with its neighborhood and prove a universality property. We relate Q(G;x,y) to other known graph invariants and graph polynomials, among them partition functions, the Tutte polynomial, the independence and matching polynomials, and the universal edge elimination polynomial introduced by I. Averbouch et al. (2008) [5].We show that Q(G;x,y) is vertex reconstructible in the sense of Kelly and Ulam, and discuss its use in computing residual connectedness reliability. Finally we show that the computation of Q(G;x,y) is #P-hard, but fixed parameter tractable for graphs of bounded tree-width and clique-width. © 2011 Elsevier Ltd.