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

Online Help

All Products    Maple    MapleSim


GraphTheory

  

IsChordal

  

test if graph is chordal

 

Calling Sequence

Parameters

Options

Description

Definition

Examples

Compatibility

Calling Sequence

IsChordal(G,opts)

Parameters

G

-

graph

opts

-

(optional) one or more options as specified below

Options

• 

eliminationordering : keyword option of the form eliminationordering=true or eliminationordering=false.

  

Specifies whether an elimination ordering should be returned when G is chordal. The default is false.

• 

usecached : keyword option of the form usecached=true or usecached=false.

  

Specifies whether previously stored information should be used, if available. The default is true.

Description

• 

The IsChordal(G) command returns true if G is a chordal graph and false otherwise.

Definition

• 

An undirected graph G is chordal if every cycle of length 4 or more has a chord, that is, an edge that is not part of the cycle but connects two vertices of the cycle.

• 

Every interval graph is a chordal graph.

• 

Every split graph is a chordal graph.

Examples

The cycle graph on four vertices is not chordal by definition, since it is a 4-cycle without a chord.

(1)

(2)

The complete graph on four vertices is chordal.

(3)

(4)

The Petersen graph is not chordal.

(5)

(6)

Compatibility

• 

The GraphTheory[IsChordal] command was introduced in Maple 2022.

• 

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

See Also

CliqueNumber

CycleBasis

 


Download Help Document