CliquePolynomial returns the clique polynomial for the graph G in the variable x.

For an undirected graph G, the clique polynomial of G is defined to be

where $\mathrm{\omega }\left(G\right)$ is the clique number of G and $c_k$ is the number of cliques in G of size $k$.

The coefficients $c_1$ and $c_2$ are equal to the number of vertices and the number of edges of G, respectively.

The clique polynomial of G is equal to the independence 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{CliquePolynomial}\left(P\,x\right)$

$\left(x+1\right)\left(1+3x\right)$

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

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

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

$5x^2+5x+1$

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

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