GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

IsGraphicSequence

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

IsGraphicSequence(L)

Parameters

L

-

list of integers

Description

• 

The IsGraphicSequence command returns true if there exists a graph with the specified degree sequence given as input. It returns false otherwise. The strategy is to verify some inequalities due to Erdős, Gallai (1960). A refinement due to Tripathi, Vijai (2003) is implemented which makes the algorithm faster.

• 

To construct a graph with given degree sequence, use SequenceGraph.

Examples

withGraphTheory:

L3,2,4,2,3,4,5,7

L3,2,4,2,3,4,5,7

(1)

IsGraphicSequenceL

true

(2)

GSequenceGraphL

GGraph 1: an undirected unweighted graph with 8 vertices and 15 edge(s)

(3)

sortDegreeSequenceG

2,2,3,3,4,4,5,7

(4)

See Also

DegreeSequence

SequenceGraph