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 $\mathrm{\alpha }\left(G\right)$ is the independence number of G and $s_k$ is the number of independent sets of size $k$.

The coefficient $s_0$ is always 1 as the empty set is the unique independent set of size 0. The coefficient $s_1$ 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.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

$P≔\mathrm{Graph}\left(\left\{\left\{1\,2\right\}\,\left\{2\,3\right\}\,\left\{3\,4\right\}\right\}\right)$

$P≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 4\; vertices\; and\; 3\; edge(s)}$

$\mathrm{IndependencePolynomial}\left(P\,x\right)$

$3x^2+4x+1$

$C≔\mathrm{CycleGraph}\left(5\right)$

$C≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 5\; edge(s)}$

$\mathrm{IndependencePolynomial}\left(C\,x\right)$

$5x^2+5x+1$

The GraphTheory[IndependencePolynomial] command was introduced in Maple 2018.

For more information on Maple 2018 changes, see Updates in Maple 2018.