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

Online Help

All Products    Maple    MapleSim


GraphTheory

  

IsComparabilityGraph

  

test if graph is a comparability graph

 

Calling Sequence

Parameters

Options

Description

Definition

Examples

Compatibility

Calling Sequence

IsComparabilityGraph(G,opts)

Parameters

G

-

graph

opts

-

(optional) one or more options as specified below

Options

• 

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

  

Specifies whether a directed graph representing a transitive orientation of G should be returned when G is a comparability graph. 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 IsComparabilityGraph(G) command returns true if G is a comparability graph and false otherwise.

Definition

• 

An undirected graph G is a comparability graph if it has a transitive orientation; that is, there exists a corresponding directed graph G2 with an identical vertex set and exactly one directed edge for each edge of G, and which also has the property that whenever there are directed edges from u to v and from v to w, there is also a directed edge from u to w.

• 

The complement of a comparability graph is an interval graph.

Examples

withGraphTheory:

The cycle graph on an even number of vertices is a comparability graph.

C4CycleGraph4

C4Graph 1: an undirected graph with 4 vertices and 4 edge(s)

(1)

IsComparabilityGraphC4

true

(2)

The cycle graph on an odd number of vertices is not a comparability graph.

C5CycleGraph5

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

(3)

IsComparabilityGraphC5

false

(4)

The complement of an interval graph is a comparability graph.

IGIntervalGraph1..4,2..3,2..6,3..7,4..9,5..8,6..9,7..9,8..10

IGGraph 3: an undirected graph with 9 vertices and 24 edge(s)

(5)

GGraphComplementIG

GGraph 4: an undirected graph with 9 vertices and 12 edge(s)

(6)

IsComparabilityGraphG

true

(7)

The Petersen graph is not a comparability graph.

PSpecialGraphs:-PetersenGraph

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

(8)

IsComparabilityGraphP

false

(9)

Compatibility

• 

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

• 

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

See Also

IsChordal

IsIntervalGraph