GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

CliqueCover

  

find a minimal vertex clique cover for a graph

  

CliqueCoverNumber

  

return the size of a minimal vertex clique cover for a graph

 

Calling Sequence

Parameters

Description

Definitions

Examples

Compatibility

Calling Sequence

CliqueCover(G)

CliqueCover(G, k)

CliqueCoverNumber(G)

Parameters

G

-

undirected graph

k

-

(optional) non-negative integer (the number of cliques)

Description

• 

The CliqueCover(G) command returns a minimum vertex clique cover for the graph G.

• 

The CliqueCover(G,k) command attempts to produce a clique cover for G of no more than k cliques. If such a partition is possible, a list of cliques is returned. If not possible, an error message is displayed.

• 

The CliqueCoverNumber(G) command returns the size of a minimum vertex clique cover for G. Note this equivalent to computing the chromatic number for the graph complement of G.

• 

The problem of finding a clique cover of size k for a graph is NP-complete, meaning that no polynomial-time algorithm is presently known. The exhaustive search will take an exponential time on some graphs.

Definitions

• 

A clique cover or vertex clique cover of a graph G is a partition of the vertices of G into cliques. That is, it is a set of mutually disjoint subsets of the vertices of G, each of which is a clique. Each clique cover is a coloring of the graph complement of G.

• 

A minimum clique cover of a graph G is a clique cover of minimum size for the graph G.

• 

The clique cover number of a graph G is the cardinality of a minimum clique cover of G. It is equal to the chromatic number of the graph complement of G.

Examples

withGraphTheory:

withSpecialGraphs:

PPetersenGraph

PGraph 1: an undirected unweighted graph with 10 vertices and 15 edge(s)

(1)

CliqueCoverP

1,2,3,4,5,8,9,10,6,7

(2)

C5CycleGraph5

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

(3)

CliqueCoverNumberC5

3

(4)

CliqueCoverC5

4,5,2,3,1

(5)

Compatibility

• 

The GraphTheory[CliqueCover] and GraphTheory[CliqueCoverNumber] commands were introduced in Maple 2016.

• 

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

See Also

ChromaticNumber

GraphTheory

GreedyColor

IsVertexColorable

MaximumClique