Construction of Graphs and Digraphs
Construction of a General Graph
Graph<n | edges: parameters> : RngIntElt, List -> GrphUnd, GrphVertSet, GrphEdgeSet
IncidenceGraph(A) : ModHomElt -> GrphUnd
Example Graph_Constructors (H102E1)
Example Graph_TutteCage (H102E2)
Construction of a General Digraph
Digraph<n | edges: parameters> : RngIntElt, List -> GrphDir
IncidenceDigraph(A) : ModHomElt -> GrphDir
Example Graph_Constructors (H102E3)
Operations on the Support
Support(G) : Grph -> SetIndx
ChangeSupport(G, S) : Grph, SetIndx -> Grph, GrphVertSet, GrphEdgeSet
ChangeSupport(~G, S) : Grph, SetIndx ->
StandardGraph(G) : Grph -> Grph
Example Graph_Constructors (H102E4)
Construction of a Standard Graph
BipartiteGraph(m, n) : RngIntElt, RngIntElt -> GrphUnd
CompleteGraph(p) : RngIntElt -> GrphUnd
KCubeGraph(k: parameters) : RngIntElt -> GrphUnd
MultipartiteGraph(Q) : [RngIntElt] -> GrphUnd
EmptyGraph(p: parameters) : RngIntElt -> GrphUnd
NullGraph(: parameters) : -> GrphUnd
PathGraph(p: parameters) : RngIntElt -> GrphUnd
PolygonGraph(p: parameters) : RngIntElt -> GrphUnd
RandomGraph(p, r: parameters) : RngIntElt, FldReElt -> GrphUnd
RandomTree(p: parameters) : RngIntElt -> GrphUnd
Construction of a Standard Digraph
CompleteDigraph(p) : RngIntElt -> GrphDir
EmptyDigraph(p: parameters) : RngIntElt -> GrphDir
RandomDigraph(p, r: parameters) : RngIntElt, FldReElt -> GrphDir
Example Graph_Constructors (H102E5)
Sparse Graphs
HasSparseRep(G) : Grph -> BoolElt
Example Graph_SparseReps (H102E6)
The Vertex--Set and Edge--Set of a Graph
Creating Edges and Vertices
EdgeSet(G) : Grph -> GrphEdgeSet
Edges(G) : Grph -> {@ GrphEdge @}
VertexSet(G) : Grph -> GrphVertSet
Vertices(G) : Grph -> { GrphVert }
V ! v : GrphVertSet, . -> GrphVert
V . i : GrphVertSet, RngIntElt -> GrphVert
Index(v) : GrphVert -> RngIntElt
E ! { u, v } : GrphEdgeSet, . -> GrphEdge
E ! [u, v] : GrphEdgeSet, [ . ] -> GrphEdge
E . i : GrphEdgeSet, RngIntElt -> GrphEdge
Example Graph_EdgeSets (H102E7)
Operations on Edges and Vertices
EndVertices(e) : GrphEdge -> { GrphVert }
InitialVertex(e) : GrphEdge -> GrphVert
TerminalVertex(e) : GrphEdge -> GrphVert
s eq t : GrphVert, GrphVert -> BoolElt
S ne T : GrphVertSet, GrphVertSet -> BoolElt
s ne t : GrphVert, GrphVert -> BoolElt
ParentGraph(S) : GrphVertSet -> Grph
ParentGraph(s) : GrphVert -> Grph
Labelling a Graph
AssignLabel(t, l) : GrphVert, . ->
AssignLabels(S, L) : [GrphVert], SeqEnum ->
AssignLabels(T, L) : GrphVertSet, SeqEnum ->
Reading Labels
Label(t) : GrphVert -> .
Labels(S) : [GrphVert] -> SeqEnum
Labels(T) : GrphVertSet -> SeqEnum
VertexLabels(G) : Grph -> SeqEnum
EdgeLabels(G) : Grph -> SeqEnum
Testing for Labels
IsLabelled(t) : GrphVert -> BoolElt
IsLabelled(T) : GrphVertSet -> BoolElt
IsVertexLabelled(G) : Grph -> BoolElt
IsEdgeLabelled(G) : Grph -> BoolElt
Deleting Labels
DeleteLabel(t) : GrphVert ->
DeleteLabels(S) : [GrphVert] ->
DeleteLabels(T) : GrphVertSet ->
UnlabelledGraph(G) : Grph -> Graph
Example Graph_Labels (H102E8)
Example Graph_CayleyGraph (H102E9)
Standard Constructions for Graphs
Subgraphs and Quotient Graphs
sub< G | list > : Grph, List -> Grph, GrphVertSet, GrphEdgeSet
quo< G | P > : Grph, { { GrphVert } } -> Grph, GrphVertSet, GrphEdgeSet
Example Graph_Subgraph (H102E10)
Example Graph_Quotient (H102E11)
Incremental Construction of Graphs
Adding Vertices
G + n : Grph, RngIntElt -> Grph
G +:= n : Grph, RngIntElt ->
AddVertex(~G, l) : Grph, . ->
AddVertices(~G, n, L) : Grph, RngIntElt, SeqEnum ->
Removing Vertices
G - v : Grph, GrphVert -> Grph
G -:= v : Grph, GrphVert ->
Adding Edges
G + { u, v } : GrphUnd, { GrphVert, GrphVert }-> GrphUnd, GrphEdge
G + { { u, v } } : GrphUnd, { { GrphVert, GrphVert } } -> GrphUnd
G +:= { u, v } : GrphUnd, { GrphVert, GrphVert } ->
AddEdge(G, u, v) : Grph, GrphVert, GrphVert -> Grph, GrphEdge
AddEdge(G, u, v, l) : Grph, GrphVer, GrphVert, . -> Grph, GrphEdge
AddEdge(~G, u, v) : Grph, GrphVert, GrphVert ->
AddEdges(~G, S, L) : Grph, SeqEnum, SeqEnum ->
Removing Edges
G - e : Grph, GrphEdge -> Grph
G - { { u, v } } : GrphUnd, { { GrphVert, GrphVert rbrace } -> GrphUnd
G -:= e : Grph, GrphEdge ->
Constructing Complements, Line Graphs; Contraction, Switching
Complement(G) : Grph -> Grph
Contract(e) : GrphEdge -> Grph
Contract(u, v) : GrphVert, GrphVert -> Grph
Contract(S) : { GrphVert } -> Grph
InsertVertex(e) : GrphEdge -> Grph
InsertVertex(T) : { GrphEdge } -> Grph
LineGraph(G) : Grph -> Grph
Switch(u) : GrphVert -> GrphUnd
Switch(S) : { GrphVert } -> Grph
Example Graph_Grotzch (H102E12)
Unions and Products of Graphs
Union(G, H) : GrphUnd, GrphUnd -> GrphUnd
EdgeUnion(G, H) : GrphDir, GrphDir -> GrphDir
CompleteUnion(G, H) : GrphDir, GrphDir -> GrphDir
CartesianProduct(G, H) : GrphDir, GrphDir -> GrphDir
LexProduct(G, H) : GrphDir, GrphDir -> GrphDir
TensorProduct(G, H) : GrphDir, GrphDir -> GrphDir
G ^ n : GrphUnd, RngIntElt -> GrphUnd
Converting between Graphs and Digraphs
OrientatedGraph(G) : GrphUnd -> GrphDir
UnderlyingGraph(D) : GrphDir -> GrphUnd
UnderlyingDigraph(G) : GrphUnd -> GrphDir
Construction from Groups, Codes and Designs
Graphs Constructed from Groups
CayleyGraph(A) : Grp -> GrphDir
SchreierGraph(A, B) : Grp, Grp -> GrphDir
OrbitalGraph(P, u, T) : GrpPerm, RngIntElt, { RngIntElt } -> GrphUnd
ClosureGraph(P, G) : GrpPerm, GrphUnd -> GrphUnd
PaleyGraph(q) : RngIntElt -> GrphUnd
PaleyTournament(q) : RngIntElt -> GrphDir
Graphs Constructed from Designs
IncidenceGraph(D) : Inc -> GrphUnd
PointGraph(D) : Inc -> GrphUnd
BlockGraph(D) : Inc -> GrphUnd
IncidenceGraph(P) : Plane -> GrphUnd;
PointGraph(P) : Plane -> GrphUnd;
LineGraph(P) : Plane -> GrphUnd
HadamardGraph(H: parameters) : Mtrx -> GrphUnd
Miscellaneous Graph Constructions
Converse(G) : GrphDir -> GrphDir
OddGraph(n) : RngIntElt -> GrphUnd
TriangularGraph(n) : RngIntElt -> GrphUnd
SquareLatticeGraph(n) : RngIntElt -> GrphUnd
ClebschGraph() : -> GrphUnd
ChangGraphs() : -> [GrpUnd, GrpUnd, GrpUnd]
Elementary Invariants of a Graph
Order(G) : Grph -> RngIntElt
Size(G) : Grph -> RngIntElt
CharacteristicPolynomial(G) : GrphUnd -> RngUPolElt
Spectrum(G) : GrphUnd -> SetEnum
Elementary Graph Predicates
u adj v : GrphVert, GrphVert -> BoolElt
e adj f : GrphEdge, GrphEdge -> BoolElt
u notadj v : GrphVert, GrphVert -> BoolElt
e notadj f : GrphEdge, GrphEdge -> BoolElt
u in e : GrphVert, GrphEdge -> BoolElt
u notin e : GrphVert, GrphEdge -> BoolElt
G eq H : GrphDir, GrphDir -> BoolElt
IsSubgraph(G, H) : Grph, Grph -> BoolElt
IsBipartite(G) : GrphUnd -> BoolElt
IsComplete(G) : Grph -> BoolElt
IsEulerian(G) : Grph -> BoolElt
IsForest(G) : GrphUnd -> BoolElt
IsEmpty(G) : Grph -> BoolElt
IsNull(G) : Grph -> BoolElt
IsPath(G) : Grph -> BoolElt
IsPolygon(G) : Grph -> BoolElt
IsRegular(G) : Grph -> BoolElt
IsTree(G) : Grph -> BoolElt
Adjacency, Degree and Distance
Adjacency, Degree and Distance Functions for a Graph
Alldeg(G, n) : GrphUnd, RngIntElt -> { GrphVert }
Ball(u, n) : GrphVert, RngIntElt -> { GrphVert }
Bipartition(G) : GrphUnd -> [ { GrphVert } ]
Degree(u) : GrphVert -> RngIntElt
DegreeSequence(G) : Grph -> [ { GrphVert } ]
Distance(u, v) : GrphVert, GrphVert -> RngIntElt
IncidentEdges(u) : GrphVert -> { GrphEdge }
MaximumDegree(G) : GrphUnd -> RngIntElt, GrphVert
MinimumDegree(G) : GrphUnd -> RngIntElt, GrphVert
Neighbours(u) : GrphVert -> { GrphVert }
Sphere(u, n) : GrphVert, RngIntElt -> { GrphVert }
Valence(G) : GrphUnd -> RngIntElt
MinimumDominatingSet(G) : GrphUnd -> SetEnum
Adjacency and Degree Functions for a Digraph
u adj v : GrphVert, GrphVert -> BoolElt
e adj f : GrphEdge, GrphEdge -> BoolElt
u notadj v : GrphVert, GrphVert -> BoolElt
e notadj f : GrphEdge, GrphEdge -> BoolElt
u in e : GrphVert, GrphEdge -> BoolElt
Alldeg(G, n) : GrphDir, RngIntElt -> { GrphVert }
Ball(u, n) : Vert, RngIntElt -> { GrphVert }
Degree(u) : GrphVert -> RngIntElt
InDegree(u) : GrphVert -> RngIntElt
InNeighbours(u) : GrphVert -> { GrphVert }
MaximumDegree(G) : GrphDir -> RngIntElt, GrphVert
MaximumInDegree(G) : GrphDir -> RngIntElt, GrphVert
MaximumOutDegree(G) : GrphDir -> RngIntElt, GrphVert
MinimumDegree(G) : GrphDir -> RngIntElt, GrphVert
MinimumInDegree(G) : GrphDir -> RngIntElt, GrphVert
MinimumOutDegree(G) : GrphDir -> RngIntElt, GrphVert
OutDegree(u) : GrphVert -> RngIntElt
OutNeighbours(u) : GrphVert -> { GrphVert }
Connectedness, Paths and Circuits
Connectedness in a Graph
IsConnected(G) : GrphUnd -> BoolElt
Components(G) : Grph -> [ { GrphVert } ]
Component(u) : GrphVert -> Grph
IsSeparable(G) : GrphUnd -> BoolElt
IsBiconnected(G) : GrphUnd -> BoolElt
CutVertices(G) : Grph -> { GrphVert }
Bicomponents(G) : GrphUnd -> [GrphUnd]
Graph Triconnectivity
IsTriconnected(G) : GrphUnd -> BoolElt
Splitcomponents(G) : GrphUnd -> [ { GrphVert } ], [ [ GrphVert ]]
SeparationVertices(G) : GrphUnd -> [ [ GrphVert ]], [ { GrphVert } ]
Example Graph_Triconnectivity (H102E13)
Maximum Matching in Bipartite Graphs
MaximumMatching(G) : Grph -> [ { GrphEdge } ]
Example Graph_MaxMatching (H102E14)
Paths and Circuits in a Graph
Diameter(G) : Grph -> RngIntElt
DiameterPath(G) : Grph -> [GrphVert]
Distance(u, v) : GrphVert, GrphVert -> RngIntElt
DistancePartition(u) : GrphVert -> [ { GrphVert } ]
IsEquitable(G, P) : GrphUnd, { { GrphVert } } -> BoolElt
EquitablePartition(P, G) : { { GrphVert } }, GrphUnd -> { { GrphVert } }
[Future release] EulerianCircuit(G) : GrphUnd -> [GrphVert]
Geodesic(u, v) : GrphVert, GrphVert -> [GrphVert]
Girth(G) : GrphUnd -> RngIntElt
GirthCycle(G) : GrphUnd -> [GrphVert]
Reachable(u, v) : GrphVert, GrphVert -> BoolElt
Connectedness, Paths and Circuits in a Digraph
Component(u) : GrphVert -> Grph
IsStronglyConnected(G) : GrphDir -> BoolElt
IsWeaklyConnected(G) : GrphDir -> BoolElt
StronglyConnectedComponents(G) : GrphUnd -> [GrphDir]
DistancePartition(u) : GrphVert -> [ { GrphVert } ]
General Vertex and Edge Connectivity in Graphs and Digraphs
VertexSeparator(G) : Grph -> [ { GrphVert } ]
VertexConnectivity(G) : Grph -> RngIntElt, [ { GrphVert } ]
IsKVertexConnected(G, k) : Grph, RngIntElt -> BoolElt
EdgeSeparator(G) : Grph -> [ { GrphEdge } ]
EdgeConnectivity(G) : Grph -> RngIntElt, [ { GrphEdge } ]
IsKEdgeConnected(G, k) : Grph, RngIntElt -> BoolElt
Example Graph_Connectivity (H102E15)
Matrices and Vector Spaces Associated with a Graph or Digraph
AdjacencyMatrix(G) : Grph -> AlgMatElt
[Future release] CircuitSpace(G) : GrphUnd -> ModTup
DistanceMatrix(G) : Grph -> AlgMatElt
IncidenceMatrix(G) : Grph -> ModHomElt
IntersectionMatrix(G, P) : GrphUnd, { { GrphVert } } -> AlgMatElt
Spanning Trees of a Graph or Digraph
SpanningTree(G) : GrphUnd -> Grph
SpanningForest(G) : Grph -> Grph
BreadthFirstSearchTree(u) : GrphVert -> Grph
DepthFirstSearchTree(u) : GrphVert -> Grph
Directed Trees
IsRootedTree(G) : GrphDir -> BoolElt, GrphVert
Root(G) : GrphDir -> GrphVert
IsRoot(v) : GrphVert -> BoolElt
RootSide(v) : GrphVert -> GrphVert
VertexPath(u,v) : GrphVert,GrphVert -> SeqEnum
BranchVertexPath(u,v) : GrphVert,GrphVert -> SeqEnum
Colourings
ChromaticNumber(G) : GrphUnd -> RngIntElt
OptimalVertexColouring(G) : GrphUnd -> SeqEnum
ChromaticIndex(G) : GrphUnd -> RngIntElt
OptimalEdgeColouring(G) : GrphUnd -> SeqEnum
ChromaticPolynomial(G) : GrphUnd -> RngUPolElt
Example Graph_ChromaticNumber (H102E16)
Cliques, Independent Sets
HasClique(G, k) : GrphUnd, RngIntEl -> BoolElt, { GrphVert }
HasClique(G, k, m: parameters) : GrphUnd, RngIntEl, BoolElt -> BoolElt, { GrphVert }
HasClique(G, k, m, f: parameters) : GrphUnd, RngIntEl, BoolElt, RngIntEl -> BoolElt, { GrphVert }
MaximumClique(G: parameters) : GrphUnd -> { GrphVert }
CliqueNumber(G: parameters) : GrphUnd -> RngIntElt
AllCliques(G) : GrphUnd -> SeqEnum
AllCliques(G, k) : GrphUnd, RngIntEl -> SeqEnum
AllCliques(G, k, m: parameters) : GrphUnd, RngIntElt, BoolElt -> SeqEnum
MaximumIndependentSet(G: parameters) : GrphUnd -> { GrphVert }
IndependenceNumber(G: parameters) : GrphUnd -> RngIntElt
Example Graph_Cliques (H102E17)
Planar Graphs
IsPlanar(G) : GraphUnd -> BoolElt, GrphUnd
Obstruction(G) : GraphUnd -> GrphUnd
IsHomeomorphic(G: parameters) : GraphUnd -> BoolElt
Faces(G) : GraphUnd -> SeqEnum[GrphVert]
Face(u, v) : GrphVert, GrphVert -> SeqEnum
Face(e) : GrphEdge -> SeqEnum
NFaces(G) : GraphUnd -> RngIntElt
Embedding(G) : GraphUnd -> SeqEnum
Embedding(v) : GrphVert -> SeqEnum
Example Graph_Planarity (H102E18)
Automorphism Group of a Graph or Digraph
The Automorphism Group Function
AutomorphismGroup( G: parameters) : Grph -> GrpPerm, GSet, GSet, PowMap, Map, Grph
nauty Invariants
IsPartitionRefined(G: parameters) : Grph -> BoolElt
Graph Colouring and Automorphism Group
Variants of Automorphism Group
CanonicalGraph(G) : Grph -> Grph
EdgeGroup(G) : Grph -> GrpPerm, GSet
IsIsomorphic(G, H) : GrphDir, GrphDir -> BoolElt, Map
Example Graph_AutomorphismGroup (H102E19)
Example Graph_GraphIsomorphim (H102E20)
Action of Automorphisms
Image(a, Y, y) : GrpPermElt, GSet, Elt -> Elt
Orbit(A, Y, y) : GrpPerm, GSet, Elt -> GSet
Orbits(A, Y) : GrpPerm, GSet -> [ GSet ]
Stabilizer(A, Y, y) : GrpPerm, Elt -> GrpPerm
Action(A, Y) : GrpPerm, GSet -> Hom(Grp), GrpPerm, GrpPerm
ActionImage(A, Y) : GrpPerm, GSet -> GrpPerm
ActionKernel(A, Y) : GrpPerm, GSet -> GrpPerm
Example Graph_AutomorphismAction (H102E21)
Symmetry and Regularity Properties of Graphs
IsTransitive(G) : GrphUnd -> BoolElt
IsEdgeTransitive(G) : GrphUnd -> BoolElt
OrbitsPartition(G) : GrphUnd -> [ { GrphVert } ]
IsPrimitive(G) : GrphUnd -> BoolElt
IsSymmetric(G) : GrphUnd -> BoolElt
[Future release] IsArcTransitive(G, t) : GrphUnd, RngIntElt -> BoolElt
IsDistanceTransitive(G) : GrphUnd -> BoolElt
IsDistanceRegular(G) : GrphUnd -> BoolElt
IntersectionArray(G) : GrphUnd -> [RngIntElt]
Example Graph_Regularity (H102E22)
Graph Database and Graph Generation
Strongly Regular Graphs
StronglyRegularGraphsDatabase() : -> DB
Classes(D) : DB -> SeqEnum
NumberOfClasses(D) : DB -> RngIntElt
NumberOfGraphs(D) : DB -> RngIntElt
NumberOfGraphs(D, S) : DB, SeqEnum -> RngIntElt
Graphs(D, S) : DB, SeqEnum -> SeqEnum
Graph(D, S, i) : DB, SeqEnum, RngIntElt -> GrphUnd
RandomGraph(D) : DB -> GrphUnd
RandomGraph(D, S) : DB, SeqEnum -> GrphUnd
Example Graph_StronglyRegularGraphs (H102E23)
Generating Graphs
GenerateGraphs(n : parameters) : RngIntElt -> File
NextGraph(F: parameters) : File -> BoolElt, GrphUnd
Example Graph_GraphGeneration (H102E24)
A General Facility
OpenGraphFile(s, f, p): MonStgElt, RngIntElt, RngIntElt -> File