A survey on recurrence relations for the independence polynomial of hypergraphs

DOI10.1007/S00373-016-1685-ZzbMATH Open1349.05173arXiv1406.2990OpenAlexW2277921154MaRDI QIDQ343776FDOQ343776

Authors: Martin Trinks 

Publication date: 29 November 2016

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

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.

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

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

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• 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)