IndependencePolynomial - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


GraphTheory

  

IndependencePolynomial

  

compute independence polynomial

 

Calling Sequence

Parameters

Description

Definition

Examples

Compatibility

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

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.

Examples

withGraphTheory:

withSpecialGraphs:

PGraph1,2,2,3,3,4

PGraph 1: an undirected graph with 4 vertices and 3 edge(s)

(1)

IndependencePolynomialP,x

3x2+4x+1

(2)

CCycleGraph5

CGraph 2: an undirected graph with 5 vertices and 5 edge(s)

(3)

IndependencePolynomialC,x

5x2+5x+1

(4)

Compatibility

• 

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