GraphTheory - Maple Programming Help

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

GraphTheory

 IndependencePolynomial
 compute independence polynomial

 Calling Sequence IndependencePolynomial(G, x)

Parameters

 G - undirected graph x - variable or value

Description

 • IndependencePolynomial returns the independence polynomial for the graph G in the variable x.

Definition

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

$\sum _{k=0}^{\mathrm{\alpha }\left(G\right)}{s}_{k}{x}^{k}$

 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.

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{IndependencePolynomial}\left(P,x\right)$
 ${3}{}{{x}}^{{2}}{+}{4}{}{x}{+}{1}$ (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{IndependencePolynomial}\left(C,x\right)$
 ${5}{}{{x}}^{{2}}{+}{5}{}{x}{+}{1}$ (4)

Compatibility

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