Mathematics – Combinatorics
Scientific paper
2008-12-22
Mathematics
Combinatorics
23 pages, 9 figures, Minor corrections of misprints and new open problems
Scientific paper
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, B. Godlin and J.A. Makowsky (2008). We show that $Q(G;x,y)$ is vertex reconstructible in the sense of Kelly and Ulam, discuss its use in computing residual connectedness reliability. Finally we show that the computation of $Q(G;x,y)$ is $\sharp \mathbf{P}$-hard, but Fixed Parameter Tractable for graphs of bounded tree-width and clique-width.
Averbouch Ilia
Makowsky Johann A.
Tittmann Peter
No associations
LandOfFree
The Enumeration of Vertex Induced Subgraphs with respect to the Number of Components does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Enumeration of Vertex Induced Subgraphs with respect to the Number of Components, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Enumeration of Vertex Induced Subgraphs with respect to the Number of Components will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-538716