A survey on recurrence relations for the independence polynomial of hypergraphs

2014/06/11 by Martin Trinks, Trinks, Martin · 1 citation
Computer Science · Mathematics · #05C30 #05C31 #05C65 #05C69 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Graph theory and applications #math.CO #msc:05C30 #msc:05C31 #msc:05C65 #msc:05C69

paper · pdf · doi:10.48550/arxiv.1406.2990

14 pages

arxiv created 2014/06/11 · openalex publication_date 2014/06/11 · arxiv updated 2014/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region

Related

• Recurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs
• An Efficiently Computable Lower Bound for the Independence Number of Hypergraphs
• Independence densities of hypergraphs
• The independence polynomial on recursive sequences of graphs
• A note on the values of independence polynomials at -1