GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

CliquePolynomial

  

compute clique polynomial

 

Calling Sequence

Parameters

Description

Definition

Examples

Compatibility

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+k=1ωGckxk

  

where ωG is the clique number of G and ck is the number of cliques in G of size k.

• 

The coefficients c1 and c2 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

withGraphTheory:

withSpecialGraphs:

PGraph1,2,2,3,3,4

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

(1)

CliquePolynomialP,x

1+x1+3x

(2)

CCycleGraph5

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

(3)

CliquePolynomialC,x

5x2+5x+1

(4)

Compatibility

• 

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

• 

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

See Also

CliqueNumber

IndependencePolynomial