Optimal Graphs for Independence and k-Independence Polynomials

2017/10/09 by Jason I. Brown, Brown, J. I., Danielle Cox +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1710.03249

openalex publication_date 2017/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The independence polynomial I(G,x) of a finite graph G is the generating function for the sequence of the number of independent sets of each cardinality. We investigate whether, given a fixed number of vertices and edges, there exists optimally-least (optimally-greatest) graphs, that are least (respectively, greatest) for all non-negative x. Moreover, we broaden our scope to k-independence polynomials, which are generating functions for the k-clique-free subsets of vertices. For k ≥ 3, the results can be quite different from the k = 2 (i.e. independence) case.

Cited by

• Cardinalities of the total number of independent sets

Related

• Minimizing the number of independent sets in triangle-free regular graphs
• The independence polynomial of a graph at -1
• A Linear Algorithm for Computing Independence Polynomials of Trees
• On the Stability of Independence Polynomials
• MAX for k-independence in multigraphs