Construction of Graphs and Digraphs
Construction of a General Graph
Graph<p | edges> : RngIntElt, List -> GrphUnd
IncidenceGraph(A) : ModHomElt -> GrphUnd
Example Graph_Constructors (H93E1)
Example Graph_TutteCage (H93E2)
Construction of a General Digraph
Digraph<p | edges> : RngIntElt, List -> GrphDir
IncidenceDigraph(A) : ModHomElt -> GrphDir
Example Graph_Constructors (H93E3)
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 (H93E4)
Construction of a Standard Graph
BipartiteGraph(m, n) : RngIntElt, RngIntElt -> GrphUnd
CompleteGraph(p) : RngIntElt -> GrphUnd
KCubeGraph(k) : RngIntElt -> GrphUnd
MultipartiteGraph(Q) : [RngIntElt] -> GrphUnd
EmptyGraph(p) : RngIntElt -> GrphUnd
PathGraph(p) : RngIntElt -> GrphUnd
PolygonGraph(p) : RngIntElt -> GrphUnd
RandomGraph(p, r) : RngIntElt, FldReElt -> GrphUnd
RandomTree(p) : RngIntElt -> GrphUnd
Construction of a Standard Digraph
CompleteDigraph(p) : RngIntElt -> GrphDir
EmptyDigraph(p) : RngIntElt -> GrphDir
RandomDigraph(p, r) : RngIntElt, FldReElt -> GrphDir
Example Graph_Constructors (H93E5)
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 (H93E6)
Operations on Edges and Vertices
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, . ->
AssignLabel(G, i, l) : Grph, RngIntElt, . ->
AssignLabel(G, i, j, l) : Grph, RngIntElt, RngIntElt, . ->
AssignLabels(S, L) : [GrphVert], SeqEnum ->
AssignLabels(G, S, L) : Grph, [RngIntElt], SeqEnum ->
AssignLabels(G, S, L) : Grph, SeqEnum, SeqEnum ->
AssignLabels(T, L) : GrphVertSet, SeqEnum ->
Reading Labels
Label(t) : GrphVert -> .
VertexLabel(G, i) : Grph, RngIntElt -> .
EdgeLabel(G, i, j) : Grph, RngIntElt, RngIntElt -> .
Labels(S) : [GrphVert] -> SeqEnum
Labels(T) : GrphVertSet -> SeqEnum
VertexLabels(G, S) : Grph, [RngIntElt] -> SeqEnum
VertexLabels(G) : Grph -> SeqEnum
EdgeLabels(G, S) : Grph, SeqEnum -> SeqEnum
EdgeLabels(G) : Grph -> SeqEnum
Testing for Labels
IsLabelled(t) : GrphVert -> BoolElt
IsLabelledVertex(G, i) : Grph, RngIntElt -> BoolElt
IsLabelledEdge(G, i, j) : Grph, RngIntElt, RngIntElt -> BoolElt
Deleting Labels
DeleteLabel(t) : GrphVert ->
DeleteLabel(G, i) : Grph, RngIntElt ->
DeleteLabel(G, i, j) : Grph, RngIntElt, RngIntElt ->
DeleteLabels(S) : [GrphVert] ->
DeleteLabels(G, S) : Grph, [RngIntElt] ->
DeleteLabels(G, S) : Grph, SeqEnum ->
DeleteLabels(T) : GrphVertSet ->
Example Graph_Labels (H93E7)
Example Graph_CayleyGraph (H93E8)
Standard Constructions for Graphs
Subgraphs, Quotient Graphs, and Super-graphs
sub< G | v_1, ..., v_r > : Grph, List(Vert) -> Grph, GrphVertSet, GrphEdgeSet
sub< G | e_1, ..., e_r > : Grph, List(Edge) -> Grph, GrphVertSet, GrphEdgeSet
G - v : Grph, GrphVert -> Grph
G - U : Grph, { GrphVert } -> Grph
G - e : Grph, GrphEdge -> Grph
G - F : Grph, { GrphEdge } -> Grph
G + { u, v } : GrphUnd, { GrphVert } -> GrphUnd
G + [u, v] : GrphDir, [GrphVert] -> GrphDir
G + S : GrphUnd, { { GrphVert } } -> GrphUnd
G + S : GrphDir, { [GrphVert] } -> GrphDir
quo< G | P > : Grph, { { GrphVert } } -> Grph, GrphVertSet, GrphEdgeSet
Example Graph_Labels (H93E9)
Example Graph_Quotient (H93E10)
Incremental Construction of Graphs
AddVertex(~G) : Grph ->
AddVertex(~G, l) : Grph, . ->
AddVertices(~G, n) : Grph, RngIntElt ->
AddVertices(~G, n, L) : Grph, RngIntElt, SeqEnum ->
RemoveVertex(~G, i) : Grph, RngIntElt ->
RemoveVertices(~G, S) : Grph, [RngIntElt] ->
AddEdge(~G, i, j) : Grph, RngIntElt, RngIntElt ->
AddEdge(~G, i, j, l) : Grph, RngIntElt, RngIntElt, . ->
AddEdges(~G, S) : Grph, SeqEnum ->
AddEdges(~G, S, L) : Grph, SeqEnum, SeqEnum ->
RemoveEdge(~G, i, j) : Grph, RngIntElt, RngIntElt ->
RemoveEdges(~G, S) : Grph, SeqEnum ->
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 (H93E11)
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 of Graphs 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
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
IsBipartite(G) : GrphUnd -> BoolElt
IsComplete(G) : Grph -> BoolElt
IsConnected(G) : GrphUnd -> BoolElt
IsEulerian(G) : Grph -> BoolElt
IsForest(G) : GrphUnd -> BoolElt
IsEmpty(G) : Grph -> BoolElt
IsPath(G) : Grph -> BoolElt
IsPolygon(G) : Grph -> BoolElt
[Future release] IsPlanar(G) : GrphUnd -> BoolElt
IsRegular(G) : Grph -> BoolElt
IsSeparable(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
EndVertices(e) : GrphEdge -> { GrphVert }
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
EndVertices(e) : GrphEdge -> [GrphVert]
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 }
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
Connectedness, Paths and Circuits
Connectedness, Paths and Circuits in a Graph
Bicomponents(G) : GrphUnd -> [GrphUnd]
Component(u) : GrphVert -> Grph
Components(G) : Grph -> [ { GrphVert } ]
CutVertices(G) : Grph -> { GrphVert }
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
[Future release] Tricomponents(G) : GrphUnd -> { { GrphVert } }
Connectedness, Paths and Circuits in a Digraph
IsStronglyConnected(G) : GrphDir -> BoolElt
IsWeaklyConnected(G) : GrphDir -> BoolElt
DistancePartition(u) : GrphVert -> [ { GrphVert } ]
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
SpanningForest(G) : Grph -> Grph
SpanningTree(G) : Grph -> Grph
BreadthFirstSearchTree(u) : GrphVert -> Grph
DepthFirstSearchTree(u) : GrphVert -> Grph
Colourings
ChromaticNumber(G) : GrphUnd -> RngIntElt
OptimalVertexColouring(G) : GrphUnd -> SeqEnum
ChromaticIndex(G) : GrphUnd -> RngIntElt
OptimalEdgeColouring(G) : GrphUnd -> SeqEnum
ChromaticPolynomial(G) : GrphUnd -> RngUPolElt
Example Graph_ChromaticNumber (H93E12)
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 (H93E13)
Automorphism Group of a Graph or Digraph
The Automorphism Group Function
AutomorphismGroup( G: parameters) : Grph -> GrpPerm, GSet, GSet, PowMap, Map, Grph
nauty Invariants
TestNautyInvariant(G: parameters) : Grph -> BoolElt
Graph Colouring and Parameter Setting: A General Discussion
Variants of Automorphism Group
CanonicalGraph(G : parameters ) : Grph -> Grph
EdgeGroup(G : parameters ) : Grph -> GrpPerm, GSet
IsIsomorphic(G, H : parameters ) : GrphDir, GrphDir -> BoolElt, Map
Example Graph_AutomorphismGroup (H93E14)
Example Graph_GraphIsomorphim (H93E15)
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 (H93E16)
Symmetry and Regularity Properties of Graphs
IsTransitive(G : parameters) : GrphUnd -> BoolElt
IsEdgeTransitive(G : parameters) : GrphUnd -> BoolElt
OrbitsPartition(G : parameters ) : GrphUnd -> [ { GrphVert } ]
IsPrimitive(G : parameters) : GrphUnd -> BoolElt
IsSymmetric(G : parameters) : GrphUnd -> BoolElt
[Future release] IsArcTransitive(G, t) : GrphUnd, RngIntElt -> BoolElt
IsDistanceTransitive(G : parameters) : GrphUnd -> BoolElt
IsDistanceRegular(G) : GrphUnd -> BoolElt
IntersectionArray(G) : GrphUnd -> [RngIntElt]
Example Graph_AutomorphismGroup (H93E17)
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 (H93E18)
Generating Graphs
GenerateGraphs(n : parameters) : RngIntElt -> File
NextGraph(F) : File -> BoolElt, GrphUnd
Example Graph_GraphGeneration (H93E19)
A General Facility
OpenGraphFile(s, f, p): MonStgElt, RngIntElt, RngIntElt -> File