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

DOI10.1016/j.ejc.2011.03.017zbMath1229.05124arXiv0812.4147OpenAlexW2027446053MaRDI QIDQ648958

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

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

Related Items (16)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• The interlace polynomial of a graph
• From a zoo to a zoology: Towards a general theory of graph polynomials
• An extension of the bivariate chromatic polynomial
• Computing optimal assignments for residual network reliability
• Interlace polynomials
• Recursively constructible families of graphs
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Graphs determined by polynomial invariants
• On graphs determined by their Tutte polynomials
• Upper bounds to the clique width of graphs
• Counting truth assignments of formulas of bounded tree-width or clique-width
• 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
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Complexity of the Bollobás-Riordan Polynomial
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• A Most General Edge Elimination Polynomial – Thickening of Edges
• Graph reconstruction—a survey
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• Community structure in social and biological networks
• On the computational complexity of the Jones and Tutte polynomials
• A Subset Expansion of the Coloured Tutte Polynomial
• On the Complexity of the Interlace Polynomial
• A Most General Edge Elimination Polynomial
• Complexity of the Cover Polynomial
• Linear Recurrence Relations for Graph Polynomials
• Graph-Theoretic Concepts in Computer Science
• Logical Approaches to Computational Barriers
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

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