 GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/CliquePolynomial

GraphTheory

 CliquePolynomial
 compute clique polynomial

 Calling Sequence CliquePolynomial(G, x)

Parameters

 G - undirected graph x - variable or value

Description

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

Definition

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

$1+\left(\sum _{k=1}^{\mathrm{\omega }\left(G\right)}{c}_{k}{x}^{k}\right)$

 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.

Examples

 > $\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 unweighted graph with 4 vertices and 3 edge\left(s\right)}}$ (1)
 > $\mathrm{CliquePolynomial}\left(P,x\right)$
 $\left({1}{+}{x}\right){}\left({1}{+}{3}{}{x}\right)$ (2)
 > $C≔\mathrm{CycleGraph}\left(5\right)$
 ${C}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 5 vertices and 5 edge\left(s\right)}}$ (3)
 > $\mathrm{CliquePolynomial}\left(C,x\right)$
 ${5}{}{{x}}^{{2}}{+}{5}{}{x}{+}{1}$ (4)

Compatibility

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