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

DOI10.1016/J.EJC.2011.03.017zbMATH Open1229.05124OpenAlexW2027446053MaRDI QIDQ648958FDOQ648958

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) Graph polynomials (05C31) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Enumeration in graph theory (05C30) 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

• 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?)
• A Most General Edge Elimination Polynomial
• A Subset Expansion of the Coloured Tutte Polynomial
• A most general edge elimination polynomial -- thickening of edges
• 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
• Interlace polynomials
• Linear Recurrence Relations for Graph Polynomials
• Logical Approaches to Computational Barriers
• On graphs determined by their Tutte polynomials
• On the Complexity of the Interlace Polynomial
• On the colored Tutte polynomial of a graph of bounded treewidth
• 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

(17)

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

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)