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

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

Authors: Juan-Miguel Gracia 

Publication date: 29 November 2011

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

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.

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

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

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)

Cites Work

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

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)