The enumeration of vertex induced subgraphs with respect to the number of components

DOI10.1016/J.EJC.2011.03.017MaRDI QIDQ648958zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 29 November 2011

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.4147

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Graph polynomials (05C31) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Reliability, testing and fault tolerance of networks and computer systems (68M15)

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, 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 $sharpmathbfP$-hard, but Fixed Parameter Tractable for graphs of bounded tree-width and clique-width.

Recommendations

• A graph polynomial arising from community structure (extended abstract)
• scientific article; zbMATH DE number 6890347
• scientific article; zbMATH DE number 6813595
• Note on the subgraph component polynomial
• Counting connected set partitions of graphs

Cites work

• A Most General Edge Elimination Polynomial
• A most general edge elimination polynomial -- thickening of edges
• A Subset Expansion of the Coloured Tutte Polynomial
• A survey of some network reliability analysis and synthesis results
• Algorithmic uses of the Feferman-Vaught theorem
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• An extension of the bivariate chromatic polynomial
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Community structure in social and biological networks
• Complexity of the Bollobás-Riordan Polynomial
• Complexity of the Cover Polynomial
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Computing optimal assignments for residual network reliability
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Graph polynomials: from recursive definitions to subset expansion formulas
• Graph reconstruction—a survey
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph-Theoretic Concepts in Computer Science
• Graphs determined by polynomial invariants
• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• scientific article; zbMATH DE number 3784908 (Why is no real title available?)
• scientific article; zbMATH DE number 17789 (Why is no real title available?)
• scientific article; zbMATH DE number 48089 (Why is no real title available?)
• scientific article; zbMATH DE number 176250 (Why is no real title available?)
• scientific article; zbMATH DE number 2038883 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 2121498 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Interlace polynomials
• Linear Recurrence Relations for Graph Polynomials
• Logical Approaches to Computational Barriers
• On graphs determined by their Tutte polynomials
• On the colored Tutte polynomial of a graph of bounded treewidth
• On the Complexity of the Interlace Polynomial
• On the computational complexity of the Jones and Tutte polynomials
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Recursively constructible families of graphs
• Reflection positivity, rank connectivity, and homomorphism of graphs
• The interlace polynomial of a graph
• The structure and dynamics of networks
• Upper bounds to the clique width of graphs

Cited in

(22)

• Border correlations, lattices, and the subgraph component polynomial
• On the differential polynomial of a graph
• The behavior of Tutte polynomials of graphs under five graph operations and its applications
• Squares and primitivity in partial words
• On sequences of polynomials arising from graph invariants
• On the weighted safe set problem on paths and cycles
• Border correlations, lattices, and the subgraph component polynomial
• Strongly polynomial sequences as interpretations
• Note on the subgraph component polynomial
• An abstraction of Whitney's broken circuit theorem
• Polynomial reconstruction of the matching polynomial
• Alliance polynomial of regular graphs
• A graph polynomial arising from community structure (extended abstract)
• Distinguishing graphs by their left and right homomorphism profiles
• Meta-theorems for graph polynomials
• Distribution of the null coefficients of the differential polynomial of the tree graphs
• Number of facets of symmetric edge polytopes arising from join graphs
• My writing
• Graph polynomials and local graph operations
• On the location of roots of graph polynomials
• Combinatorics on partial word borders
• Polynomial graph invariants from homomorphism numbers

This page was built for publication: The enumeration of vertex induced subgraphs with respect to the number of components

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648958)