compute independence polynomial
variable or value
IndependencePolynomial returns the independence polynomial for the graph G in the variable x.
For an undirected graph G, the independence polynomial of G is defined to be
where α⁡G is the independence number of G and sk is the number of independent sets of size k.
The coefficient s0 is always 1 as the empty set is the unique independent set of size 0. The coefficient s1 is equal to the number of vertices of G.
The independence polynomial of G is equal to the clique polynomial of the graph complement of G.
P ≔ Graph⁡1,2,2,3,3,4
P≔Graph 1: an undirected graph with 4 vertices and 3 edge(s)
C ≔ CycleGraph⁡5
C≔Graph 2: an undirected graph with 5 vertices and 5 edge(s)
The GraphTheory[IndependencePolynomial] command was introduced in Maple 2018.
For more information on Maple 2018 changes, see Updates in Maple 2018.
Download Help Document