Introduction

 
Construction of Graphs and Digraphs

      Bounds on the Graph Order
            GraphSizeInBytes(n, m : parameters): RngIntElt, RngIntElt -> RngIntElt
            Example Graph_Grph_Size (H162E1)

      Construction of a General Graph
            Graph< n | edges : parameters> : RngIntElt, List -> GrphUnd, GrphVertSet, GrphEdgeSet
            IncidenceGraph(A) : ModMatRngElt -> GrphUnd
            Example Graph_Constructors (H162E2)
            Example Graph_TutteCage (H162E3)

      Construction of a General Digraph
            Digraph< n | edges : parameters> : RngIntElt, List -> GrphDir
            IncidenceDigraph(A) : ModMatRngElt -> GrphDir
            Example Graph_Constructors (H162E4)

      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 (H162E5)

      Construction of a Standard Graph
            BipartiteGraph(m, n) : RngIntElt, RngIntElt -> GrphUnd
            CompleteGraph(n) : RngIntElt -> GrphUnd
            KCubeGraph(n : parameters) : RngIntElt -> GrphUnd
            MultipartiteGraph(Q) : [RngIntElt] -> GrphUnd
            EmptyGraph(n : parameters) : RngIntElt -> GrphUnd
            NullGraph( : parameters) : -> GrphUnd
            PathGraph(n : parameters) : RngIntElt -> GrphUnd
            PolygonGraph(n : parameters) : RngIntElt -> GrphUnd
            RandomGraph(n, r : parameters) : RngIntElt, FldReElt -> GrphUnd
            RandomTree(n : parameters) : RngIntElt -> GrphUnd

      Construction of a Standard Digraph
            CompleteDigraph(n) : RngIntElt -> GrphDir
            EmptyDigraph(n : parameters) : RngIntElt -> GrphDir
            RandomDigraph(n, r : parameters) : RngIntElt, FldReElt -> GrphDir
            Example Graph_Constructors (H162E6)

 
Graphs with a Sparse Representation
      HasSparseRep(G) : Grph -> BoolElt
      Example Graph_SparseReps (H162E7)

 
The Vertex--Set and Edge--Set of a Graph

      Introduction

      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 (H162E8)

      Operations on Vertex-Sets and Edge-Sets
            # S : GrphVertSet -> RngIntElt
            s in S : GrphVert, GrphVertSet -> BoolElt
            s notin S : GrphVert, GrphVertSet -> BoolElt
            S subset T : GrphVertSet, GrphVertSet -> BoolElt
            S notsubset T : GrphVertSet, GrphVertSet -> BoolElt
            S eq T : GrphVertSet, GrphVertSet -> BoolElt
            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
            Random(S) : GrphVertSet -> GrphVert
            Representative(S) : GrphVertSet -> GrphVert
            for x in S do ... end for;
            for random x in S do ... end for;

      Operations on Edges and Vertices
            EndVertices(e) : GrphEdge -> { GrphVert }
            InitialVertex(e) : GrphEdge -> GrphVert
            TerminalVertex(e) : GrphEdge -> GrphVert
            IncidentEdges(u) : GrphVert -> { GrphEdge }

 
Labelled, Capacitated and Weighted Graphs

 
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 (H162E9)
            Example Graph_Quotient (H162E10)

      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, GrphVert, GrphVert, . -> Grph, GrphEdge
                  AddEdge(~G, u, v) : Grph, GrphVert, GrphVert ->
                  AddEdges(G, S) : GrphUnd, { { GrphVert, GrphVert } } -> GrphUnd
                  AddEdges(G, S, L) : Grph, SeqEnum, SeqEnum -> Grph
                  AddEdges(~G, S) : GrphUnd, { { GrphVert, GrphVert } } ->

            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 (H162E11)

 
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) : Grph -> GrphUnd
      UnderlyingDigraph(G) : Grph -> GrphDir

 
Construction from Groups, Codes and Designs

      Graphs Constructed from Groups
            CayleyGraph(A : parameter) : Grp -> Grph, GrphVertSet, GrphEdgeSet
            SchreierGraph(A, B) : Grp, Grp -> Grph, GrphVertSet, GrphEdgeSet
            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 and Degree

      Adjacency and Degree Functions for a Graph
            Degree(u) : GrphVert -> RngIntElt
            Alldeg(G, n) : GrphUnd, RngIntElt -> { GrphVert }
            MaximumDegree(G) : GrphUnd -> RngIntElt, GrphVert
            MinimumDegree(G) : GrphUnd -> RngIntElt, GrphVert
            DegreeSequence(G) : Grph -> [ { GrphVert } ]
            Valence(G) : GrphUnd -> RngIntElt
            Neighbours(u) : GrphVert -> { GrphVert }
            IncidentEdges(u) : GrphVert -> { GrphEdge }
            Bipartition(G) : GrphUnd -> [ { GrphVert } ]
            MinimumDominatingSet(G) : GrphUnd -> SetEnum

      Adjacency and Degree Functions for a Digraph
            InDegree(u) : GrphVert -> RngIntElt
            OutDegree(u) : GrphVert -> RngIntElt
            Degree(u) : GrphVert -> RngIntElt
            Alldeg(G, n) : GrphDir, RngIntElt -> { GrphVert }
            MaximumInDegree(G) : GrphDir -> RngIntElt, GrphVert
            MaximumOutDegree(G) : GrphDir -> RngIntElt, GrphVert
            MinimumInDegree(G) : GrphDir -> RngIntElt, GrphVert
            MinimumOutDegree(G) : GrphDir -> RngIntElt, GrphVert
            MaximumDegree(G) : GrphDir -> RngIntElt, GrphVert
            MinimumDegree(G) : GrphDir -> RngIntElt, GrphVert
            DegreeSequence(G) : Grph -> [ { GrphVert } ]
            InNeighbours(u) : GrphVert -> { GrphVert }
            OutNeighbours(u) : GrphVert -> { GrphVert }
            IncidentEdges(u) : GrphVert -> { GrphEdge }

 
Connectedness

      Connectedness in a Graph
            IsConnected(G) : GrphUnd -> BoolElt
            Components(G) : GrphUnd -> [ { GrphVert } ]
            Component(u) : GrphVert -> Grph
            IsSeparable(G) : GrphUnd -> BoolElt
            IsBiconnected(G) : GrphUnd -> BoolElt
            CutVertices(G) : Grph -> { GrphVert }
            Bicomponents(G) : GrphUnd -> [GrphUnd]

      Connectedness in a Digraph
            IsStronglyConnected(G) : GrphDir -> BoolElt
            IsWeaklyConnected(G) : GrphDir -> BoolElt
            StronglyConnectedComponents(G) : GrphDir -> [ { GrphVert } ]
            Component(u) : GrphVert -> Grph

      Graph Triconnectivity
            IsTriconnected(G) : GrphUnd -> BoolElt
            Splitcomponents(G) : GrphUnd -> [ { GrphVert } ], [ [ GrphVert ]]
            SeparationVertices(G) : GrphUnd -> [ [ GrphVert ]], [ { GrphVert } ]
            Example Graph_Triconnectivity (H162E12)

      Maximum Matching in Bipartite Graphs
            MaximumMatching(G) : GrphUnd -> [ { GrphEdge } ]
            Example Graph_MaxMatching (H162E13)

      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 (H162E14)

 
Distances, Paths and Circuits in a Graph

      Distances, Paths and Circuits in a Possibly Weighted Graph
            Reachable(u, v) : GrphVert, GrphVert -> BoolElt
            Distance(u, v) : GrphVert, GrphVert -> RngIntElt
            Geodesic(u, v) : GrphVert, GrphVert -> [GrphVert]

      Distances, Paths and Circuits in a Non-Weighted Graph
            Diameter(G) : Grph -> RngIntElt
            DiameterPath(G) : Grph -> [GrphVert]
            Ball(u, n) : GrphVert, RngIntElt -> { GrphVert }
            Sphere(u, n) : GrphVert, RngIntElt -> { GrphVert }
            DistancePartition(u) : GrphVert -> [ { GrphVert } ]
            IsEquitable(G, P) : GrphUnd, { { GrphVert } } -> BoolElt
            EquitablePartition(P, G) : { { GrphVert } }, GrphUnd -> { { GrphVert } }
            Girth(G) : GrphUnd -> RngIntElt
            GirthCycle(G) : GrphUnd -> [GrphVert]

 
Maximum Flow, Minimum Cut, and Shortest Paths

 
Matrices and Vector Spaces Associated with a Graph or Digraph
      AdjacencyMatrix(G) : Grph -> AlgMatElt
      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, GrphVertSet, GrphEdgeSet
      SpanningForest(G) : Grph -> Grph, GrphVertSet, GrphEdgeSet
      BreadthFirstSearchTree(u) : GrphVert -> Grph, GrphVertSet, GrphEdgeSet
      DepthFirstSearchTree(u) : GrphVert -> Grph, GrphVertSet, GrphEdgeSet, SeqEnum

 
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 (H162E15)

 
Cliques, Independent Sets
      HasClique(G, k) : GrphUnd, RngIntElt -> BoolElt, { GrphVert }
      HasClique(G, k, m : parameters) : GrphUnd, RngIntElt, BoolElt -> BoolElt, { GrphVert }
      HasClique(G, k, m, f : parameters) : GrphUnd, RngIntElt, BoolElt, RngIntElt -> BoolElt, { GrphVert }
      MaximumClique(G : parameters) : GrphUnd -> { GrphVert }
      CliqueNumber(G : parameters) : GrphUnd -> RngIntElt
      AllCliques(G : parameters) : GrphUnd -> SeqEnum
      AllCliques(G, k : parameters) : GrphUnd, RngIntElt -> SeqEnum
      AllCliques(G, k, m : parameters) : GrphUnd, RngIntElt, BoolElt -> SeqEnum
      MaximumIndependentSet(G: parameters) : GrphUnd -> { GrphVert }
      IndependenceNumber(G: parameters) : GrphUnd -> RngIntElt
      Example Graph_Cliques (H162E16)

 
Planar Graphs
      IsPlanar(G) : GrphUnd -> BoolElt, GrphUnd
      Obstruction(G) : GrphUnd -> GrphUnd
      IsHomeomorphic(G : parameters) : GrphUnd -> BoolElt
      Faces(G) : GrphUnd -> SeqEnum[GrphVert]
      Face(u, v) : GrphVert, GrphVert -> SeqEnum
      Face(e) : GrphEdge -> SeqEnum
      NFaces(G) : GrphUnd -> RngIntElt
      Embedding(G) : GrphUnd -> SeqEnum
      Embedding(v) : GrphVert -> SeqEnum
      PlanarDual(G) : GrphUnd -> GrphUnd
      Example Graph_Planarity (H162E17)

 
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 : parameters ) : GrphDir, GrphDir -> BoolElt, Map
            Example Graph_AutomorphismGroup (H162E18)
            Example Graph_GraphIsomorphim (H162E19)

      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, GSet, 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 (H162E20)

 
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
      IsDistanceTransitive(G) : GrphUnd -> BoolElt
      IsDistanceRegular(G) : GrphUnd -> BoolElt
      IntersectionArray(G) : GrphUnd -> [RngIntElt]
      Example Graph_Regularity (H162E21)

 
Graph Databases 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
            for G in D do ... end for;
            Example Graph_StronglyRegularGraphs (H162E22)

      Small Graphs

            Creation of Small Graph Databases
                  SmallGraphDatabase(n : parameters) : RngIntElt -> DB
                  EulerianGraphDatabase(n : parameters) : RngIntElt -> DB
                  PlanarGraphDatabase(n) : RngIntElt -> DB
                  SelfComplementaryGraphDatabase(n) : RngIntElt -> DB

            Access functions
                  # D : DB -> RngIntElt
                  Graph(D, i) : DB, RngIntElt -> GrphUnd
                  Random(D) : DB -> GrphUnd
                  for G in D do ... end for;

      Generating Graphs
            GenerateGraphs(n : parameters) : RngIntElt -> IO
            NextGraph(I: parameters) : IO -> BoolElt, GrphUnd
            Example Graph_GraphGeneration (H162E23)

      A General Facility
            OpenGraphFile(s, f, p): MonStgElt, RngIntElt, RngIntElt -> IO
            Example Graph_GraphGeneralAccess (H162E24)

 
Bibliography

[Next][Prev] [Right] [____] [Up] [Index] [Root]