GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

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 unweighted graph with 4 vertices and 3 edge(s)

(1)

IndependencePolynomialP,x

3x2+4x+1

(2)

CCycleGraph5

CGraph 2: an undirected unweighted 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