GraphTheory
IndependencePolynomial
compute independence polynomial
Calling Sequence
Parameters
Description
Definition
Examples
Compatibility
IndependencePolynomial(G, x)
G
-
undirected graph
x
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
∑k=0αGskxk
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.
withGraphTheory:
withSpecialGraphs:
P≔Graph1,2,2,3,3,4
P≔Graph 1: an undirected graph with 4 vertices and 3 edge(s)
IndependencePolynomialP,x
3x2+4x+1
C≔CycleGraph5
C≔Graph 2: an undirected graph with 5 vertices and 5 edge(s)
IndependencePolynomialC,x
5x2+5x+1
The GraphTheory[IndependencePolynomial] command was introduced in Maple 2018.
For more information on Maple 2018 changes, see Updates in Maple 2018.
See Also
CliquePolynomial
IndependenceNumber
Download Help Document