GraphTheory
A substantial effort was put into Graph Theory for Maple 2024, including new commands for graph computation and generation.

> with GraphTheory :New commands
These commands are new for Maple 2024:
AllGraphs

Condensation

FindAsteroidalTriple

IsArchimedeanGraph

IsAsteroidalTripleFree

IsDominatingSet

IsIndependentSet

MinCutMoralGraph

RelationGraph

WienerIndex

AllGraphs
The new AllGraphs command returns an iterator with which one can step through all graphs matching a particular set ofcriteria, such as vertex count or edge count. It is also possible to cause the Iterator to return only connected graphs or onlygraphs which are not isomorphic to a graph previously returned by this Iterator.

> iterator d AllGraphs vertices = 3, nonisomorphic> iterator:-getNext
Graph 1: an undirected graph with 3 vertices and 0 edge(s)> iterator:-getNext
Graph 2: an undirected graph with 3 vertices and 1 edge(s)> iterator:-getNext
Graph 3: an undirected graph with 3 vertices and 2 edge(s)Condensation
The new command Condensation computes the condensation of a given (directed) graph.
The condensation of a graph G is a graph C whose vertices correspond to the strongly connected components of G. Thecondensation C will have an arc from u to v whenever there is an arc from the strongly connected component of G
corresponding to u to the strongly connected component of G corresponding to v.

> T d Digraph 4,1, 2 , 1, 3 , 2, 3 , 3, 2 , 4, 3
T d Graph 4: a directed graph with 4 vertices and 5 arc(s)> C d Condensation T
C d Graph 5: a directed graph with 3 vertices and 2 arc(s)> DrawGraph~ T C , stylesheet = vertexpadding = 20

FindAsteroidalTriple and IsAsteroidalTripleFree
The new command FindAsteriodalTriple searches for an asteroidal triple in the given graph. The related new command
IsAsteroidalTripleFree returns true when the given graph does not contain an asteroidal triple.
An asteroidal triple for a graph G is a triple u, v, w of non-adjacent vertices of G such that for each pair from the triple,
there exists a path between them that does not intersect the third vertex or any of its neighbors.

> C6 d CycleGraph 6
C6 d Graph 6: an undirected graph with 6 vertices and 6 edge(s)> DrawGraph C6, size = 200, 200
6152

43

> FindAsteroidalTriple C61, 3, 5

IsArchimedeanGraph
The new command IsArchimedeanGraph tests whether a given graph is an Archimedean graph.
The Archimedean graphs are those graphs which form the skeletons of the Archimedean solids. TheArchimedean solids comprise 13 convex polyhedra whose faces are regular polygons and whose vertices are all
symmetric to each other, but which are not Platonic solids (polyhedra whose faces are identical).
> IsArchimedeanGraph SpecialGraphs:-SnubCubeGraph
trueIsDominatingSet
The new command IsDominatingSet tests whether a set is a dominating set for a given graph.
A dominating set of a graph G is a subset S of the vertices of G, with the condition that every vertex in G must
either be an element of S or the neighbor of an element of S.
> P5 d PathGraph 5P5 d Graph 7: an undirected graph with 5 vertices and 4 edge(s)> S3 d 1, 3, 5S3 d 1, 3, 5
> IsDominatingSet P5, S3 ;trueMinCut
The new MinCut command works per the Max-Flow Min-Cut Theorem and uses the flow output to compute a cutset. The EdgeConnectivity and VertexConnectivity commands have been updated to use MinCut so that they can
now also return cut-sets.
> MG d Graph

1, 2 , 1, 3 , 2, 3 , 2, 4 , 3, 4 , 3, 5 , 3, 6 , 3, 7 , 4, 7
MG d Graph 8: an undirected graph with 7 vertices and 9 edge(s)>mf, flowM d MaxFlow MG, 2, 7 ; i

The MinCut command will call MaxFlow by default but can reuse the flow matrix if MaxFlow has been called already.

> MinCut MG, 2, 7, flows = flowM ;3, 7 , 4, 7
> EdgeConnectivity MG, output = cutset ;3, 5> VertexConnectivity MG, output = cutset ;3

MoralGraph
The moral graph of a directed graph G is a graph M with the same vertices as G but with all directed edges madeundirected, and with the property that whenever two directed edges in G share a destination vertex, then their source
vertices are connected in M.
The new command MoralGraph constructs the moral graph given a directed graph.

> DG d Graph 7,1, 3 , 2, 3 , 2, 4 , 3, 5 , 3, 6 , 3, 7 , 4, 7, vertexpositions =1, 2 , 2, 2 , 1, 1 , 2, 1 , 0, 0 , 1, 0 , 2, 0

DG d Graph 9: a directed graph with 7 vertices and 7 arc(s)> NumberOfEdges DG
7> MG d MoralGraph DG
MG d Graph 10: an undirected graph with 7 vertices and 9 edge(s)> NumberOfEdges MG
9> SetVertexPositions MG, GetVertexPositions DG> plots:-display DrawGraph~ DG MG

512

12343467675

RelationGraph
The RelationGraph command constructs a graph on a given vertex list in which an edge is present in the graph whenevera particular Boolean predicate on its two vertices is true.

> RG d RelationGraphseq 1 ..16 , NumberTheory:-AreCoprime
RG d Graph 11: an undirected graph with 16 vertices and 79 edge(s)> DrawGraph RG
1
16

2

15

3

14

4

13

5

12

6

11

7
10

8
9

In this example, the neighborhood of the element 5 will be all those vertices whose values are coprime with 5:> Neighborhood RG, 5
1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16

WienerIndex
The WienerIndex command computes the Wiener index on a given graph. The Wiener index of a graph is the sum of thelengths of the shortest paths between all pairs of vertices in the graph.

> G d CycleGraph 20
G d Graph 12: an undirected graph with 20 vertices and 20 edge(s)> WienerIndex G40

New functionality for existing commands
Distance and ShortestPath
The Distance and ShortestPath commands now use the edge weights of a weighted matrix. They both have a new
option ignoreweights to compute the distance or shortest path in the underlying unweighted graph.
> W6 d Graph

1, 2 , 10 ,1, 6 , 6 ,2, 3 ,L10 ,3, 4 , 10 ,4, 5 ,L10 ,5, 6 , 5;W6 d Graph 13: a directed weighted graph with 6 vertices and 6 arc(s)> DrawGraph W6, layout = circle ;
1
106

6

2-10
5

5

3-10

10

4
> ShortestPath W6, 1, 6 ;1, 2, 3, 4, 5, 6
> Distance W6, 1, 6 ;5> ShortestPath W6, 1, 6, 'ignoreweights' ;1, 6> Distance W6, 1, 6, 'ignoreweights' ;1MaxFlow
The MaxFlow command now works on all graphs. It now treats an unweighted graph as a graph with all edge
weights equal to 1, or to the edge multiplicity for multigraphs.

Additions to SpecialGraphs
The SpecialGraphs subpackage now includes commands for all the Archimedean graphs, as well as the Möbius laddergraph and the Wagner graph.

Archimedean Graphs
The Archimedean graphs are those graphs which form the skeletons of the Archimedean solids. The
Archimedean solids comprise 13 convex polyhedra whose faces are regular polygons and whose vertices are all
symmetric to each other, but which are not Platonic solids (polyhedra whose faces are identical). They were first
enumerated by Archimedes.
The new command IsArchimedeanGraph tests whether a given graph is an Archimedean graph.
The following new commands generate each of the Archimedean graphs.

ArchimedeansolidDeg
ree

Vert Edices ges

Command

2-D> DrawPlanar G,> G d SpecialGraphs:-showlabels = false

3-D> DrawGraph G,
dimension=3

TruncatedTetrahedronGraph;truncatedtetrahedon

31218Gd
Graph 14: an undirected graphwith 12 vertices and 18 edge(s)> letters dseq "ABCDEFGHIJKL"> DrawPlanar G,
showlabels = false

letters d "A", "B", "C", "D", "E",> DrawGraph G,dimension=3"F", "G", "H", "I", "J", "K", "L"cuboctahedron41224> G d SpecialGraphs:CuboctahedronGraphletters
Gd
Graph 15: an undirected graphwith 12 vertices and 24 edge(s)> DrawPlanar G,
showlabels = false> DrawGraph G,
dimension=3> G d SpecialGraphs:TruncatedCubeGraph
truncated
cube

32436Gd
Graph 16: an undirected graphwith 24 vertices and 36 edge(s)> DrawPlanar G,
showlabels = false> G d SpecialGraphs:-> DrawGraph G,
dimension=3

TruncatedOctahedronGraphtruncatedoctahedron

32436

Gd
Graph 17: an undirected graphwith 24 vertices and 36 edge(s)> DrawPlanar G,
showlabels = false> G d SpecialGraphs:SmallRhombicuboctahedron\smallrhombicuboctahedron

Graph
42448

Gd
Graph 18: an undirected graphwith 24 vertices and 48 edge(s)> DrawGraph G,
dimension=3

> DrawPlanar G,
showlabels = false> G d SpecialGraphs:greatrhombicuboctahedron(also calledtruncatedcuboctahedron)> DrawGraph G,
dimension=3

GreatRhombicuboctahedron\Graph34872

Gd
Graph 19: an undirected graphwith 48 vertices and 72 edge(s)> DrawPlanar G,
showlabels = false> DrawGraph G,
dimension=3> G d SpecialGraphs:SnubCubeGraphsnub cube

52460

Gd
Graph 20: an undirected graphwith 24 vertices and 60 edge(s)> DrawPlanar G,
showlabels = false> DrawGraph G,
dimension=3> G d SpecialGraphs:IcosidodecahedronGraph
Icosidodecahedron

43060

Gd
Graph 21: an undirected graphwith 30 vertices and 60 edge(s)> DrawPlanar G,
showlabels = false> G d SpecialGraphs:-> DrawGraph G,
dimension=3TruncatedDodecahedronGr\truncateddodecahedron

aph
36090

Gd
Graph 22: an undirected graphwith 60 vertices and 90 edge(s)> DrawPlanar G,
showlabels = false> G d SpecialGraphs:TruncatedIcosahedronGraph
truncatedicosahedron

360

90

Gd
Graph 23: an undirected graphwith 60 vertices and 90 edge(s)> DrawGraph G,
dimension=3

> DrawPlanar G,
showlabels = false> G d SpecialGraphs:-> DrawGraph G,
dimension=3

SmallRhombicosidodecahed\smallrhombicosido
decahedronronGraph
460120Gd
Graph 24: an undirected graphwith 60 vertices and 120 edge(s)> DrawPlanar G,showlabels = false
greatrhombicosido
decahedron(also calledtruncatedicosidodecahedron)> G d SpecialGraphs:-> DrawGraph G,dimension=3

GreatRhombicosidodecahed\ronGraph
3120

180

GdGraph 25: an undirected graphwith 120 vertices and 180 edge(s)> DrawPlanar G,
showlabels = false> G d SpecialGraphs:-> DrawGraph G,
dimension=3

SnubDodecahedronGraphsnubdodecahedron

560

150 G dGraph 26: an undirected graphwith 60 vertices and 150 edge(s)Möbius ladder graph and Wagner graphThe Möbius ladder graph on 2 n vertices may be understood visually as the ladder graph on the same vertices, with theaddition of two edges: one connecting the left-hand side of the "op rung to the right-hand side of the bottom rung, and one
connecting the right-hand side of the top rung to the left-hand side of the bottom rung.

> WG : ML3 d SpecialGraphs:-MoebiusLadderGraph 3
ML3 d Graph 27: an undirected graph with 6 vertices and 9 edge(s)> DrawGraph ML3, stylesheet = vertexpadding = 8563412The Wagner graph is a 3-regular graph which is a particular instance of an Möbius ladder graph on 8 vertices.

> WG d SpecialGraphs:-WagnerGraph
WG d Graph 28: an undirected graph with 8 vertices and 12 edge(s)> DrawGraph WG, stylesheet = vertexpadding = 878563412