A survey on recurrence relations for the independence polynomial of hypergraphs

DOI10.1007/S00373-016-1685-ZMaRDI QIDQ343776zbMATHOpenAlexFDO

Authors Martin Trinks

Publication date 29 November 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

edge operationhypergraphindependence polynomialrecurrence relationindependent setsvertex operation

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Hypergraphs (05C65)

Abstract: The independence polynomial of a hypergraph is the generating function for its independent (vertex) sets with respect to their cardinality. This article aims to discuss several recurrence relations for the independence polynomial using some vertex and edge operations. Further, an extension of the well-known recurrence relation for simple graphs to hypergraphs is proven and other novel recurrence relations are also discussed.

Recommendations

• Recursion relations for chromatic coefficients for graphs and hypergraphs
• An algorithm for finding the independence number of a recursively generated hypergraph
• Recurrence relations for graph polynomials on bi-iterative families of graphs
• On the matching polynomial of hypergraphs
• An algorithm for calculating the independence and vertex-cover polynomials of a graph

Cites work

• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 166023 (Why is no real title available?)
• Clique polynomials and independent set polynomials of graphs
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• The Merrifield-Simmons conjecture holds for bipartite graphs
• The covered components polynomial: a new representation of the edge elimination polynomial
• The vertex-cover polynomial of a graph
• Theory of monomer-dimer systems

Cited in

(4)

• Independence polynomials and hypergeometric series
• On the matching polynomial of hypergraphs
• Independence polynomials of bipartite graphs
• On \(P\)-unique hypergraphs

This page was built for publication: A survey on recurrence relations for the independence polynomial of hypergraphs

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