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) 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)

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

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)