GAP (Digraphs) - Chapter 3: Creating digraphs

Every digraph in Digraphs belongs to the category IsDigraph. Some basic attributes and operations for digraphs are DigraphVertices (5.1-1), DigraphEdges (5.1-3), and OutNeighbours (5.2-6).

3.1-2 IsMutableDigraph

IsMutableDigraph is a synonym for IsDigraph (3.1-1) and IsMutable (Reference: IsMutable). A mutable digraph may be changed in-place by methods in the Digraphs package, and is not attribute-storing – see IsAttributeStoringRep (Reference: IsAttributeStoringRep).

A mutable digraph may be converted into an immutable attribute-storing digraph by calling MakeImmutable (Reference: MakeImmutable) on the digraph.

3.1-3 IsImmutableDigraph

IsImmutableDigraph is a subcategory of IsDigraph (3.1-1). Digraphs that lie in IsImmutableDigraph are immutable and attribute-storing. In particular, they lie in IsAttributeStoringRep (Reference: IsAttributeStoringRep).

A mutable digraph may be converted to an immutable digraph that lies in the category IsImmutableDigraph by calling MakeImmutable (Reference: MakeImmutable) on the digraph.

The operation DigraphMutableCopy (3.3-1) can be used to construct a mutable copy of an immutable digraph. It is however not possible to convert an immutable digraph into a mutable digraph in-place.

3.1-4 IsCayleyDigraph

IsCayleyDigraph is a subcategory of IsDigraph. Digraphs that are Cayley digraphs of a group and that are constructed by the operation CayleyDigraph (3.1-12) are constructed in this category, and are always immutable.

3.1-5 IsDigraphWithAdjacencyFunction

IsDigraphWithAdjacencyFunction is a subcategory of IsDigraph. Digraphs that are created using an adjacency function are constructed in this category.

3.1-6 DigraphByOutNeighboursType

The type of all digraphs is DigraphByOutNeighboursType. The family of all digraphs is DigraphFamily.

3.1-7 Digraph

If the optional first argument filt is present, then this should specify the category or representation the digraph being created will belong to. For example, if filt is IsMutableDigraph (3.1-2), then the digraph being created will be mutable, if filt is IsImmutableDigraph (3.1-3), then the digraph will be immutable. If the optional first argument filt is not present, then IsImmutableDigraph (3.1-3) is used by default.

gap> gr := Digraph([
> [2, 5, 8, 10], [2, 3, 4, 2, 5, 6, 8, 9, 10], [1],
> [3, 5, 7, 8, 10], [2, 5, 7], [3, 6, 7, 9, 10], [1, 4],
> [1, 5, 9], [1, 2, 7, 8], [3, 5]]);
<immutable multidigraph with 10 vertices, 38 edges>
gap> gr := Digraph(["a", "b", "c"], ["a"], ["b"]);
<immutable digraph with 3 vertices, 1 edge>
gap> gr := Digraph(5, [1, 2, 2, 4, 1, 1], [2, 3, 5, 5, 1, 1]);
<immutable multidigraph with 5 vertices, 6 edges>
gap> Petersen := Graph(SymmetricGroup(5), [[1, 2]], OnSets,
> function(x, y) return Intersection(x, y) = []; end);;
gap> Digraph(Petersen);
<immutable digraph with 10 vertices, 30 edges>
gap> gr := Digraph([1 .. 10], ReturnTrue);
<immutable digraph with 10 vertices, 100 edges>
gap> Digraph("Diamond");
<immutable digraph with 4 vertices, 10 edges>

The next example illustrates the uses of the fourth and fifth variants of this constructor. The resulting digraph is a strongly regular graph, and it is actually the point graph of the van Lint-Schrijver partial geometry, [vLS81]. The algebraic description is taken from the seminal paper of Calderbank and Kantor [CK86].

gap> f := GF(3 ^ 4);
GF(3^4)
gap> gamma := First(f, x -> Order(x) = 5);
Z(3^4)^64
gap> L := Union([Zero(f)], List(Group(gamma)));
[ 0*Z(3), Z(3)^0, Z(3^4)^16, Z(3^4)^32, Z(3^4)^48, Z(3^4)^64 ]
gap> omega := Union(List(L, x -> List(Difference(L, [x]), y -> x - y)));
[ Z(3)^0, Z(3), Z(3^4)^5, Z(3^4)^7, Z(3^4)^8, Z(3^4)^13, Z(3^4)^15, 
  Z(3^4)^16, Z(3^4)^21, Z(3^4)^23, Z(3^4)^24, Z(3^4)^29, Z(3^4)^31, 
  Z(3^4)^32, Z(3^4)^37, Z(3^4)^39, Z(3^4)^45, Z(3^4)^47, Z(3^4)^48, 
  Z(3^4)^53, Z(3^4)^55, Z(3^4)^56, Z(3^4)^61, Z(3^4)^63, Z(3^4)^64, 
  Z(3^4)^69, Z(3^4)^71, Z(3^4)^72, Z(3^4)^77, Z(3^4)^79 ]
gap> adj := function(x, y)
>   return x - y in omega;
> end;
function( x, y ) ... end
gap> digraph := Digraph(AsList(f), adj);
<immutable digraph with 81 vertices, 2430 edges>
gap> group := Group(Z(3));;
gap> act := \*;
<Operation "*">
gap> digraph := Digraph(group, List(f), act, adj);
<immutable digraph with 81 vertices, 2430 edges>

3.1-8 DigraphByAdjacencyMatrix

If list is the adjacency matrix of a digraph in the sense of AdjacencyMatrix (5.2-1), then this operation returns the digraph which is defined by list.

Alternatively, if list is a square boolean matrix, then this operation returns the digraph with Length(list) vertices which has the edge [i,j] if and only if list[i][j] is true.

gap> DigraphByAdjacencyMatrix([
> [0, 1, 0, 2, 0],
> [1, 1, 1, 0, 1],
> [0, 3, 2, 1, 1],
> [0, 0, 1, 0, 1],
> [2, 0, 0, 0, 0]]);
<immutable multidigraph with 5 vertices, 18 edges>
gap> D := DigraphByAdjacencyMatrix([
> [true, false, true],
> [false, false, true],
> [false, true, false]]);
<immutable digraph with 3 vertices, 4 edges>
gap> OutNeighbours(D);
[ [ 1, 3 ], [ 3 ], [ 2 ] ]
gap> D := DigraphByAdjacencyMatrix(IsMutableDigraph, 
> [[true, false, true],
>  [false, false, true],
>  [false, true, false]]);
<mutable digraph with 3 vertices, 4 edges>

3.1-9 DigraphByEdges

If list is list of pairs of positive integers, then this function returns the digraph with the minimum number of vertices m such that its list equal list.

If the optional second argument n is a positive integer with n >= m (with m defined as above), then this function returns the digraph with n vertices and list list.

gap> DigraphByEdges(
> [[1, 3], [2, 1], [2, 3], [2, 5], [3, 6],
>  [4, 6], [5, 2], [5, 4], [5, 6], [6, 6]]);
<immutable digraph with 6 vertices, 10 edges>
gap> DigraphByEdges(
> [[1, 3], [2, 1], [2, 3], [2, 5], [3, 6],
>  [4, 6], [5, 2], [5, 4], [5, 6], [6, 6]], 12);
<immutable digraph with 12 vertices, 10 edges>
gap> DigraphByEdges(IsMutableDigraph, 
> [[1, 3], [2, 1], [2, 3], [2, 5], [3, 6],
>  [4, 6], [5, 2], [5, 4], [5, 6], [6, 6]], 12);
<mutable digraph with 12 vertices, 10 edges>

3.1-10 EdgeOrbitsDigraph

If G is a permutation group, edges is an edge or list of edges, and n is a non-negative integer such that G fixes [1 .. n] setwise, then this operation returns an immutable digraph with n vertices and the union of the orbits of the edges in edges under the action of the permutation group G. An edge in this context is simply a pair of positive integers.

If the optional third argument n is not present, then the largest moved point of the permutation group G is used by default.

gap> digraph := EdgeOrbitsDigraph(Group((1, 3), (1, 2)(3, 4)),
>                                 [[1, 2], [4, 5]], 5);
<immutable digraph with 5 vertices, 12 edges>
gap> OutNeighbours(digraph);
[ [ 2, 4, 5 ], [ 1, 3, 5 ], [ 2, 4, 5 ], [ 1, 3, 5 ], [  ] ]
gap> RepresentativeOutNeighbours(digraph);
[ [ 2, 4, 5 ], [  ] ]

3.1-11 DigraphByInNeighbours

If list is a list of lists of positive integers list the range [1 .. Length(list)], then this function returns the digraph with vertices \(E^0=\)[1 .. Length(list)], and edges corresponding to the entries of list. More precisely, there is an edge with source vertex i and range vertex j if i is in the list list[j].

If i occurs in the list list[j] with multiplicity k, then there are k multiple edges from i to j.

gap> D := DigraphByInNeighbours([
> [2, 5, 8, 10], [2, 3, 4, 5, 6, 8, 9, 10],
> [1], [3, 5, 7, 8, 10], [2, 5, 7], [3, 6, 7, 9, 10], [1, 4],
> [1, 5, 9], [1, 2, 7, 8], [3, 5]]);
<immutable digraph with 10 vertices, 37 edges>
gap> D := DigraphByInNeighbours([[2, 3, 2], [1], [1, 2, 3]]);
<immutable multidigraph with 3 vertices, 7 edges>
gap> D := DigraphByInNeighbours(IsMutableDigraph, 
>                               [[2, 3, 2], [1], [1, 2, 3]]);
<mutable multidigraph with 3 vertices, 7 edges>

3.1-12 CayleyDigraph

Let G be any group and let gens be a list of elements of G. This operation returns an immutable digraph that corresponds to the Cayley graph of G with respect to gens.

The vertices of the digraph correspond to the elements of G, in the order given by AsList(G). There exists an edge from vertex u to vertex v if and only if there exists a generator g in gens such that AsList(G)[u] * g = AsList(G)[v].

The labels of the vertices u, v, and the edge [u, v] are the corresponding elements AsList(G)[u], AsList(G)[v], and generator g, respectively; see DigraphVertexLabel (5.1-11) and DigraphEdgeLabel (5.1-13).

If the optional second argument gens is not present, then the generators of G are used by default.

The digraph created by this operation belongs to the category IsCayleyDigraph (3.1-4), the group G can be recovered from the digraph using GroupOfCayleyDigraph (5.5-1), and the generators gens can be obtained using GeneratorsOfCayleyDigraph (5.5-2).

gap> G := DihedralGroup(8);
<pc group of size 8 with 3 generators>
gap> CayleyDigraph(G);
<immutable digraph with 8 vertices, 24 edges>
gap> G := DihedralGroup(IsPermGroup, 8);
Group([ (1,2,3,4), (2,4) ])
gap> CayleyDigraph(G);
<immutable digraph with 8 vertices, 16 edges>
gap> digraph := CayleyDigraph(G, [()]);
<immutable digraph with 8 vertices, 8 edges>
gap> GroupOfCayleyDigraph(digraph) = G;
true
gap> GeneratorsOfCayleyDigraph(digraph);
[ () ]

3.1-13 ListNamedDigraphs

This function searches through the list of names that are currently in the Digraphs database of named digraphs. The first argument s should be a partially completed string; this function returns all completions str of the string s such that Digraph(str) will successfully return a digraph.

The optional second argument level controls the flexibility of the search. If level = 1, then only strings beginning exactly with s are returned. If level = 2, then all names containing s as a substring are returned. If level = 3, then once again a substring search is carried out, but characters that are not alphanumeric are ignored in the search.

The search is always case and whitespace insensitive, and this is also the case when applying Digraph (3.1-7) to a string.

3.2 Changing representations

3.2-1 AsBinaryRelation

If digraph is a digraph with a positive number of vertices \(n\), and no multiple edges, then this operation returns a binary relation on the points [1..n]. The pair [i,j] is in the binary relation if and only if [i,j] is an edge in digraph.

gap> D := Digraph([[3, 2], [1, 2], [2], [3, 4]]);
<immutable digraph with 4 vertices, 7 edges>
gap> AsBinaryRelation(D);
Binary Relation on 4 points

3.2-2 AsDigraph

and n is a non-negative integer, then AsDigraph attempts to construct a digraph with n vertices whose edges are determined by f.

The digraph returned by AsDigraph has for each vertex v in [1 .. n], an edge with source v and range v ^ f. If v ^ f is greater than n for any v, then fail is returned.

If the optional second argument n is not supplied, then the degree of the transformation f, the largest moved point of the permutation f, the maximum of the degree and the codegree of the partial perm f, or as applicable, is used by default.

gap> f := Transformation([4, 3, 3, 1, 7, 9, 10, 4, 2, 3]);
Transformation( [ 4, 3, 3, 1, 7, 9, 10, 4, 2, 3 ] )
gap> AsDigraph(f);
<immutable functional digraph with 10 vertices>
gap> AsDigraph(f, 4);
<immutable functional digraph with 4 vertices>
gap> AsDigraph(f, 5);
fail
gap> AsDigraph((1, 2, 3, 4)) = CycleDigraph(4);
true
gap> D := AsDigraph(IsMutableDigraph, (1, 3)(2, 4), 5);
<mutable digraph with 5 vertices, 5 edges>
gap> DigraphEdges(D);
[ [ 1, 3 ], [ 2, 4 ], [ 3, 1 ], [ 4, 2 ], [ 5, 5 ] ]
gap> b := BinaryRelationOnPoints(
> [[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]);
Binary Relation on 5 points
gap> D := AsDigraph(b);
<immutable digraph with 5 vertices, 11 edges>

3.2-3 Graph

If digraph is a mutable or immutable digraph without multiple edges, then this operation returns a GRAPE package graph that is isomorphic to digraph.

If digraph is a multidigraph, then since GRAPE does not support multiple edges, the multiple edges will be reduced to a single edge in the result. In order words, for a multidigraph this operation will return the same as Graph(DigraphRemoveAllMultipleEdges(digraph)).

gap> Petersen := Graph(SymmetricGroup(5), [[1, 2]], OnSets,
> function(x, y) return Intersection(x, y) = []; end);;
gap> Display(Petersen);
rec(
  adjacencies := [ [ 3, 5, 8 ] ],
  group := 
   Group( [ ( 1, 2, 3, 5, 7)( 4, 6, 8, 9,10), ( 2, 4)( 6, 9)( 7,10) 
     ] ),
  isGraph := true,
  names := [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 4, 5 ], 
      [ 2, 4 ], [ 1, 5 ], [ 3, 5 ], [ 1, 4 ], [ 2, 5 ] ],
  order := 10,
  representatives := [ 1 ],
  schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 1, 2, 2 ] )
gap> Digraph(Petersen);
<immutable digraph with 10 vertices, 30 edges>
gap> Graph(last) = Petersen;
true

3.2-4 AsGraph

If digraph is a digraph, then this method returns the same as Graph (3.2-3), except that if digraph is immutable, then the result will be stored as a mutable attribute of digraph. In this latter case, when AsGraph(digraph) is called subsequently, the same GAP object will be returned as before.

gap> D := Digraph([[1, 2], [3], []]);
<immutable digraph with 3 vertices, 3 edges>
gap> G := AsGraph(D);
rec( adjacencies := [ [ 1, 2 ], [ 3 ], [  ] ], group := Group(()), 
  isGraph := true, names := [ 1 .. 3 ], order := 3, 
  representatives := [ 1, 2, 3 ], schreierVector := [ -1, -2, -3 ] )

3.2-5 AsTransformation

If digraph is a functional digraph, then AsTransformation returns the transformation which is defined by digraph. See IsFunctionalDigraph (6.2-9). Otherwise, AsTransformation(digraph) returns fail.

If digraph is a functional digraph with \(n\) vertices, then AsTransformation(digraph) will return the transformation f of degree at most \(n\) where for each \(1 \leq i \leq n\), i ^ f is equal to the unique out-neighbour of vertex i in digraph.

gap> D := Digraph([[1], [3], [2]]);
<immutable digraph with 3 vertices, 3 edges>
gap> AsTransformation(D);
Transformation( [ 1, 3, 2 ] )
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> AsTransformation(D);
Transformation( [ 2, 3, 1 ] )
gap> AsPermutation(last);
(1,2,3)
gap> D := Digraph([[2, 3], [], []]);
<immutable digraph with 3 vertices, 2 edges>
gap> AsTransformation(D);
fail

3.3 New digraphs from old

3.3-1 DigraphImmutableCopy

Each of these operations returns a new copy of digraph, of the appropriate mutability, retaining none of the attributes or properties of digraph.

gap> D := CycleDigraph(10);
<immutable cycle digraph with 10 vertices>
gap> DigraphCopy(D) = D;
true
gap> IsIdenticalObj(DigraphCopy(D), D);
false
gap> DigraphMutableCopy(D);
<mutable digraph with 10 vertices, 10 edges>

3.3-2 DigraphImmutableCopyIfImmutable

Each of these operations returns either the original argument digraph, or a new copy of digraph of the appropriate mutability, according to the mutability of digraph.

gap> C := CycleDigraph(10);
<immutable cycle digraph with 10 vertices>
gap> D := DigraphImmutableCopyIfImmutable(C);
<immutable digraph with 10 vertices, 10 edges>
gap> IsIdenticalObj(C, D);
false
gap> C = D;
true
gap> D := DigraphImmutableCopyIfMutable(C);
<immutable cycle digraph with 10 vertices>
gap> IsIdenticalObj(C, D);
true
gap> C = D;
true
gap> D := DigraphMutableCopyIfMutable(C);
<immutable cycle digraph with 10 vertices>
gap> IsMutableDigraph(D);
false
gap> D := DigraphMutableCopyIfImmutable(C);
<mutable digraph with 10 vertices, 10 edges>
gap> IsMutableDigraph(D);
true
gap> C := CycleDigraph(IsMutableDigraph, 10);
<mutable digraph with 10 vertices, 10 edges>
gap> D := DigraphImmutableCopyIfImmutable(C);
<mutable digraph with 10 vertices, 10 edges>
gap> IsIdenticalObj(C, D);
true
gap> C = D;
true
gap> D := DigraphImmutableCopyIfMutable(C);
<immutable digraph with 10 vertices, 10 edges>
gap> IsIdenticalObj(C, D);
false
gap> C = D;
true
gap> D := DigraphMutableCopyIfMutable(C);
<mutable digraph with 10 vertices, 10 edges>
gap> IsMutableDigraph(D);
true
gap> D := DigraphMutableCopyIfImmutable(C);
<mutable digraph with 10 vertices, 10 edges>
gap> IsIdenticalObj(C, D);
true
gap> IsMutableDigraph(D);
true

3.3-3 InducedSubdigraph

If digraph is a digraph, and verts is a subset of the vertices of digraph, then this operation returns a digraph constructed from digraph by retaining precisely those vertices in verts, and those edges whose source and range vertices are both contained in verts.

The vertices of the induced subdigraph are [1..Length(verts)] but the original vertex labels can be accessed via DigraphVertexLabels (5.1-12).

If digraph belongs to IsMutableDigraph (3.1-2), then digraph is modified in place. If digraph belongs to IsImmutableDigraph (3.1-3), a new immutable digraph containing the appropriate vertices and edges is returned.

gap> D := Digraph([[1, 1, 2, 3, 4, 4], [1, 3, 4], [3, 1], [1, 1]]);
<immutable multidigraph with 4 vertices, 13 edges>
gap> InducedSubdigraph(D, [1, 3, 4]);
<immutable multidigraph with 3 vertices, 9 edges>
gap> DigraphVertices(last);
[ 1 .. 3 ]
gap> D := DigraphMutableCopy(D);
<mutable multidigraph with 4 vertices, 13 edges>
gap> new := InducedSubdigraph(D, [1, 3, 4]);
<mutable multidigraph with 3 vertices, 9 edges>
gap> D = new;
true

3.3-4 ReducedDigraph

This function returns a digraph isomorphic to the subdigraph of digraph induced by the set of non-isolated vertices, i.e. the set of those vertices of digraph which are the source or range of some edge in digraph. See InducedSubdigraph (3.3-3).

The ordering of the remaining vertices of digraph is preserved, as are the labels of the remaining vertices and edges; see DigraphVertexLabels (5.1-12) and DigraphEdgeLabels (5.1-14). This can allow one to match a vertex in the reduced digraph to the corresponding vertex in digraph.

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the isolated vertices of the mutable digraph digraph are removed in-place.

gap> D := Digraph([[1, 2], [], [], [1, 4], []]);
<immutable digraph with 5 vertices, 4 edges>
gap> R := ReducedDigraph(D);
<immutable digraph with 3 vertices, 4 edges>
gap> OutNeighbours(R);
[ [ 1, 2 ], [  ], [ 1, 3 ] ]
gap> DigraphEdges(D);
[ [ 1, 1 ], [ 1, 2 ], [ 4, 1 ], [ 4, 4 ] ]
gap> DigraphEdges(R);
[ [ 1, 1 ], [ 1, 2 ], [ 3, 1 ], [ 3, 3 ] ]
gap> DigraphVertexLabel(R, 3);
4
gap> DigraphVertexLabel(R, 2);
2
gap> D := Digraph(IsMutableDigraph, [[], [3], [2]]);
<mutable digraph with 3 vertices, 2 edges>
gap> ReducedDigraph(D);
<mutable digraph with 2 vertices, 2 edges>
gap> D;
<mutable digraph with 2 vertices, 2 edges>

3.3-5 MaximalSymmetricSubdigraph

If digraph is a digraph, then MaximalSymmetricSubdigraph returns a symmetric digraph without multiple edges which has the same vertex set as digraph, and whose edge list is formed from digraph by ignoring the multiplicity of edges, and by ignoring edges [u,v] for which there does not exist an edge [v,u].

The digraph returned by MaximalSymmetricSubdigraphWithoutLoops is the same, except that loops are removed.

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place into such a digraph described above.

See IsSymmetricDigraph (6.2-14), IsMultiDigraph (6.2-11), and DigraphHasLoops (6.2-1) for more information.

gap> D := Digraph([[2, 2], [1, 3], [4], [3, 1]]);
<immutable multidigraph with 4 vertices, 7 edges>
gap> not IsSymmetricDigraph(D) and IsMultiDigraph(D);
true
gap> OutNeighbours(D);
[ [ 2, 2 ], [ 1, 3 ], [ 4 ], [ 3, 1 ] ]
gap> S := MaximalSymmetricSubdigraph(D);
<immutable symmetric digraph with 4 vertices, 4 edges>
gap> IsSymmetricDigraph(S) and not IsMultiDigraph(S);
true
gap> OutNeighbours(S);
[ [ 2 ], [ 1 ], [ 4 ], [ 3 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> MaximalSymmetricSubdigraph(D);
<mutable empty digraph with 3 vertices>
gap> D;
<mutable empty digraph with 3 vertices>

3.3-6 MaximalAntiSymmetricSubdigraph

If digraph is a digraph, then MaximalAntiSymmetricSubdigraph returns an anti-symmetric subdigraph of digraph formed by retaining the vertices of digraph, discarding any duplicate edges, and discarding any edge [i,j] of digraph where i > j and the reverse edge [j,i] is an edge of digraph. In other words, for every symmetric pair of edges [i,j] and [j,i] in digraph, where i and j are distinct, it discards the edge \([\max(i,j),\min(i,j)]\).

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place.

gap> D := Digraph([[2, 2], [1, 3], [4], [3, 1]]);
<immutable multidigraph with 4 vertices, 7 edges>
gap> not IsAntiSymmetricDigraph(D) and IsMultiDigraph(D);
true
gap> OutNeighbours(D);
[ [ 2, 2 ], [ 1, 3 ], [ 4 ], [ 3, 1 ] ]
gap> D := MaximalAntiSymmetricSubdigraph(D);
<immutable antisymmetric digraph with 4 vertices, 4 edges>
gap> IsAntiSymmetricDigraph(D) and not IsMultiDigraph(D);
true
gap> OutNeighbours(D);
[ [ 2 ], [ 3 ], [ 4 ], [ 1 ] ]
gap> D := Digraph(IsMutableDigraph, [[2], [1]]);
<mutable digraph with 2 vertices, 2 edges>
gap> MaximalAntiSymmetricSubdigraph(D);
<mutable digraph with 2 vertices, 1 edge>
gap> D;
<mutable digraph with 2 vertices, 1 edge>

3.3-7 UndirectedSpanningForest

If digraph is a digraph with at least one vertex, then UndirectedSpanningForest returns an undirected spanning forest of digraph, otherwise this attribute returns fail. See IsUndirectedSpanningForest (4.1-2) for the definition of an undirected spanning forest.

If digraph is a digraph with at least one vertex and whose MaximalSymmetricSubdigraph (3.3-5) is connected (see IsConnectedDigraph (6.6-3)), then UndirectedSpanningTree returns an undirected spanning tree of digraph, otherwise this attribute returns fail. See IsUndirectedSpanningTree (4.1-2) for the definition of an undirected spanning tree.

If digraph is immutable, then an immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place into an undirected spanning tree of digraph.

Note that for an immutable digraph that has known undirected spanning tree, the attribute UndirectedSpanningTree returns the same digraph as the attribute UndirectedSpanningForest.

gap> D := Digraph([[1, 2, 1, 3], [1], [4], [3, 4, 3]]);
<immutable multidigraph with 4 vertices, 9 edges>
gap> UndirectedSpanningTree(D);
fail
gap> forest := UndirectedSpanningForest(D);
<immutable undirected forest digraph with 4 vertices, 4 edges>
gap> OutNeighbours(forest);
[ [ 2 ], [ 1 ], [ 4 ], [ 3 ] ]
gap> IsUndirectedSpanningForest(D, forest);
true
gap> DigraphConnectedComponents(forest).comps;
[ [ 1, 2 ], [ 3, 4 ] ]
gap> DigraphConnectedComponents(MaximalSymmetricSubdigraph(D)).comps;
[ [ 1, 2 ], [ 3, 4 ] ]
gap> UndirectedSpanningForest(MaximalSymmetricSubdigraph(D))
> = forest;
true
gap> D := CompleteDigraph(4);
<immutable complete digraph with 4 vertices>
gap> tree := UndirectedSpanningTree(D);
<immutable undirected tree digraph with 4 vertices>
gap> IsUndirectedSpanningTree(D, tree);
true
gap> tree = UndirectedSpanningForest(D);
true
gap> UndirectedSpanningForest(EmptyDigraph(0));
fail
gap> D := PetersenGraph(IsMutableDigraph);
<mutable digraph with 10 vertices, 30 edges>
gap> UndirectedSpanningTree(D);
<mutable digraph with 10 vertices, 18 edges>
gap> D;
<mutable digraph with 10 vertices, 18 edges>

3.3-8 DigraphShortestPathSpanningTree

If v is a vertex in digraph and every other vertex of digraph is reachable from v, then this operation returns the shortest path spanning tree of digraph rooted at v. If there exist vertices in digraph (other than v) that are not reachable from v, then DigraphShortestPathSpanningTree returns fail. See IsReachable (5.4-19).

The shortest path spanning tree of digraph rooted at v is a subdigraph of digraph that is a directed tree, with unique source vertex v, and where for each other vertex u in digraph, the unique directed path from v to u in the tree is the lexicographically-least shortest directed path from v to u in digraph.

See IsDirectedTree (6.6-8), DigraphSources (5.1-9), and DigraphShortestPath (5.4-23).

If digraph belongs to IsMutableDigraph (3.1-2), then digraph is modified in place. If digraph belongs to IsImmutableDigraph (3.1-3), then the spanning tree is a new immutable digraph.

gap> D := Digraph([[1, 2], [3], [2, 4], [1], [2, 4]]);
<immutable digraph with 5 vertices, 8 edges>
gap> ForAll([2 .. 5], v -> IsReachable(D, 1, v));
false
gap> DigraphShortestPathSpanningTree(D, 1);
fail
gap> tree := DigraphShortestPathSpanningTree(D, 5);
<immutable directed tree digraph with 5 vertices>
gap> OutNeighbours(tree);
[ [  ], [ 3 ], [  ], [ 1 ], [ 2, 4 ] ]
gap> ForAll(DigraphVertices(D), v ->
> DigraphShortestPath(D, 5, v) = DigraphPath(tree, 5, v));
true

3.3-9 QuotientDigraph

If digraph is a digraph, and p is a partition of the vertices of digraph, then this operation returns a digraph constructed by amalgamating all vertices of digraph which lie in the same part of p.

A partition of the vertices of digraph is a list of non-empty disjoint lists, such that the union of all the sub-lists is equal to vertex set of digraph. In particular, each vertex must appear in precisely one sub-list.

The vertices of digraph in part i of p will become vertex i in the quotient, and there exists some edge in digraph with source in part i and range in part j if and only if there is an edge from i to j in the quotient. In particular, this means that the quotient of a digraph has no multiple edges. which was a change introduced in version 1.0.0 of the Digraphs package.

If digraph belongs to IsMutableDigraph (3.1-2), then digraph is modified in place. If digraph belongs to IsImmutableDigraph (3.1-3), a new immutable digraph with the above properties is returned.

gap> D := Digraph([[2, 1], [4], [1], [1, 3, 4]]);
<immutable digraph with 4 vertices, 7 edges>
gap> DigraphVertices(D);
[ 1 .. 4 ]
gap> DigraphEdges(D);
[ [ 1, 2 ], [ 1, 1 ], [ 2, 4 ], [ 3, 1 ], [ 4, 1 ], [ 4, 3 ], 
  [ 4, 4 ] ]
gap> p := [[1], [2, 4], [3]];
[ [ 1 ], [ 2, 4 ], [ 3 ] ]
gap> quo := QuotientDigraph(D, p);
<immutable digraph with 3 vertices, 6 edges>
gap> DigraphVertices(quo);
[ 1 .. 3 ]
gap> DigraphEdges(quo);
[ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ] ]
gap> QuotientDigraph(EmptyDigraph(0), []);
<immutable empty digraph with 0 vertices>

3.3-10 DigraphReverse

The reverse of a digraph is the digraph formed by reversing the orientation of each of its edges, i.e. for every edge [i, j] of a digraph, the reverse contains the corresponding edge [j, i].

DigraphReverse returns the reverse of the digraph digraph. If digraph is immutable, then a new immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place into its reverse.

gap> D := Digraph([[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]);
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphReverse(D);
<immutable digraph with 5 vertices, 11 edges>
gap> OutNeighbours(last);
[ [ 2, 3, 4 ], [ 4, 5 ], [ 1, 2, 5 ], [ 4 ], [ 2, 5 ] ]
gap> D := Digraph([[2, 4], [1], [4], [3, 4]]);
<immutable digraph with 4 vertices, 6 edges>
gap> DigraphEdges(D);
[ [ 1, 2 ], [ 1, 4 ], [ 2, 1 ], [ 3, 4 ], [ 4, 3 ], [ 4, 4 ] ]
gap> DigraphEdges(DigraphReverse(D));
[ [ 1, 2 ], [ 2, 1 ], [ 3, 4 ], [ 4, 1 ], [ 4, 3 ], [ 4, 4 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> OutNeighbours(D);
[ [ 2 ], [ 3 ], [ 1 ] ]
gap> DigraphReverse(D);
<mutable digraph with 3 vertices, 3 edges>
gap> OutNeighbours(D);
[ [ 3 ], [ 1 ], [ 2 ] ]

3.3-11 DigraphDual

The dual of digraph has the same vertices as digraph, and there is an edge in the dual from i to j whenever there is no edge from i to j in digraph. The dual is sometimes called the complement.

DigraphDual returns the dual of the digraph digraph. If digraph is an immutable digraph, then a new immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place into its dual.

gap> D := Digraph([[2, 3], [], [4, 6], [5], [],
> [7, 8, 9], [], [], []]);
<immutable digraph with 9 vertices, 8 edges>
gap> DigraphDual(D);
<immutable digraph with 9 vertices, 73 edges>
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphDual(D);
<mutable digraph with 3 vertices, 6 edges>
gap> D;
<mutable digraph with 3 vertices, 6 edges>

3.3-12 DigraphSymmetricClosure

If digraph is a digraph, then this attribute gives the minimal symmetric digraph which has the same vertices and contains all the edges of digraph.

A digraph is symmetric if its adjacency matrix AdjacencyMatrix (5.2-1) is symmetric. For a digraph with multiple edges this means that there are the same number of edges from a vertex u to a vertex v as there are from v to u; see IsSymmetricDigraph (6.2-14).

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place into its symmetric closure.

gap> D := Digraph([[1, 2, 3], [2, 4], [1], [3, 4]]);
<immutable digraph with 4 vertices, 8 edges>
gap> D := DigraphSymmetricClosure(D);
<immutable symmetric digraph with 4 vertices, 11 edges>
gap> IsSymmetricDigraph(D);
true
gap> List(OutNeighbours(D), AsSet);
[ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 4 ], [ 2, 3, 4 ] ]
gap> D := Digraph([[2, 2], [1]]);
<immutable multidigraph with 2 vertices, 3 edges>
gap> D := DigraphSymmetricClosure(D);
<immutable symmetric multidigraph with 2 vertices, 4 edges>
gap> OutNeighbours(D);
[ [ 2, 2 ], [ 1, 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphSymmetricClosure(D);
<mutable digraph with 3 vertices, 6 edges>
gap> D;
<mutable digraph with 3 vertices, 6 edges>

3.3-13 DigraphTransitiveClosure

If digraph is a digraph with no multiple edges, then these attributes return the (reflexive) transitive closure of digraph.

A digraph is reflexive if it has a loop at every vertex, and it is transitive if whenever [i,j] and [j,k] are edges of digraph, [i,k] is also an edge. The (reflexive) transitive closure of a digraph digraph is the least (reflexive and) transitive digraph containing digraph.

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place into its (reflexive) transitive closure.

Let \(n\) be the number of vertices of digraph, and let \(m\) be the number of edges. For an arbitrary digraph, these attributes will use a version of the Floyd-Warshall algorithm, with complexity \(O(n^3)\). However, for a topologically sortable digraph [see DigraphTopologicalSort (5.1-10)], these attributes will use methods with complexity \(O(m + n + m \cdot n)\) when this is faster.

gap> D := DigraphFromDiSparse6String(".H`eOWR`Ul^");
<immutable digraph with 9 vertices, 8 edges>
gap> IsReflexiveDigraph(D) or IsTransitiveDigraph(D);
false
gap> OutNeighbours(D);
[ [ 4, 6 ], [ 1, 3 ], [  ], [ 5 ], [  ], [ 7, 8, 9 ], [  ], [  ], 
  [  ] ]
gap> T := DigraphTransitiveClosure(D);
<immutable transitive digraph with 9 vertices, 18 edges>
gap> OutNeighbours(T);
[ [ 4, 6, 5, 7, 8, 9 ], [ 1, 3, 4, 5, 6, 7, 8, 9 ], [  ], [ 5 ], 
  [  ], [ 7, 8, 9 ], [  ], [  ], [  ] ]
gap> RT := DigraphReflexiveTransitiveClosure(D);
<immutable preorder digraph with 9 vertices, 27 edges>
gap> OutNeighbours(RT);
[ [ 4, 6, 5, 7, 8, 9, 1 ], [ 1, 3, 4, 5, 6, 7, 8, 9, 2 ], [ 3 ], 
  [ 5, 4 ], [ 5 ], [ 7, 8, 9, 6 ], [ 7 ], [ 8 ], [ 9 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphReflexiveTransitiveClosure(D);
<mutable digraph with 3 vertices, 9 edges>
gap> D;
<mutable digraph with 3 vertices, 9 edges>

3.3-14 DigraphTransitiveReduction

If digraph is a topologically sortable digraph [see DigraphTopologicalSort (5.1-10)] with no multiple edges, then these operations return the (reflexive) transitive reduction of digraph.

The (reflexive) transitive reduction of such a digraph is the unique least subgraph such that the (reflexive) transitive closure of the subgraph is equal to the (reflexive) transitive closure of digraph [see DigraphReflexiveTransitiveClosure (3.3-13)]. In order words, it is the least subgraph of digraph which retains the same reachability as digraph.

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place into its (reflexive) transitive reduction.

Let \(n\) be the number of vertices of an arbitrary digraph, and let \(m\) be the number of edges. Then these operations use methods with complexity \(O(m + n + m \cdot n)\).

gap> D := Digraph([[1, 2, 3], [3], [3]]);;
gap> DigraphHasLoops(D);
true
gap> D1 := DigraphReflexiveTransitiveReduction(D);
<immutable digraph with 3 vertices, 2 edges>
gap> DigraphHasLoops(D1);
false
gap> OutNeighbours(D1);
[ [ 2 ], [ 3 ], [  ] ]
gap> D2 := DigraphTransitiveReduction(D);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphHasLoops(D2);
true
gap> OutNeighbours(D2);
[ [ 2, 1 ], [ 3 ], [ 3 ] ]
gap> DigraphReflexiveTransitiveClosure(D)
>  = DigraphReflexiveTransitiveClosure(D1);
true
gap> DigraphTransitiveClosure(D)
>  = DigraphTransitiveClosure(D2);
true
gap> D := Digraph(IsMutableDigraph, [[1], [1], [1, 2, 3]]);
<mutable digraph with 3 vertices, 5 edges>
gap> DigraphReflexiveTransitiveReduction(D);
<mutable digraph with 3 vertices, 2 edges>
gap> D;
<mutable digraph with 3 vertices, 2 edges>

3.3-15 DigraphAddVertex

The operation returns a digraph constructed from digraph by adding a single new vertex, and no new edges.

If the optional second argument label is a GAP object, then the new vertex will be labelled label.

If digraph belongs to IsMutableDigraph (3.1-2), then the vertex is added directly to digraph. If digraph belongs to IsImmutableDigraph (3.1-3), an immutable copy of digraph with the additional vertex is returned.

gap> D := CompleteDigraph(3);
<immutable complete digraph with 3 vertices>
gap> new := DigraphAddVertex(D);
<immutable digraph with 4 vertices, 6 edges>
gap> D = new;
false
gap> DigraphVertices(new);
[ 1 .. 4 ]
gap> new := DigraphAddVertex(D, Group([(1, 2)]));
<immutable digraph with 4 vertices, 6 edges>
gap> DigraphVertexLabels(new);
[ 1, 2, 3, Group([ (1,2) ]) ]
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 2, 3);
<mutable digraph with 5 vertices, 12 edges>
gap> new := DigraphAddVertex(D);
<mutable digraph with 6 vertices, 12 edges>
gap> D = new;
true

3.3-16 DigraphAddVertices

For a non-negative integer m, this operation returns a digraph constructed from digraph by adding m new vertices.

Otherwise, if labels is a list consisting of k GAP objects, then this operation returns a digraph constructed from digraph by adding k new vertices, which are labelled according to this list.

If digraph belongs to IsMutableDigraph (3.1-2), then the vertices are added directly to digraph, which is changed in-place. If digraph belongs to IsImmutableDigraph (3.1-3), then digraph itself is returned if no vertices are added (i.e. m=0 or labels is empty), otherwise the result is a new immutable digraph.

gap> D := CompleteDigraph(3);
<immutable complete digraph with 3 vertices>
gap> new := DigraphAddVertices(D, 3);
<immutable digraph with 6 vertices, 6 edges>
gap> DigraphVertices(new);
[ 1 .. 6 ]
gap> new := DigraphAddVertices(D, [Group([(1, 2)]), "d"]);
<immutable digraph with 5 vertices, 6 edges>
gap> DigraphVertexLabels(new);
[ 1, 2, 3, Group([ (1,2) ]), "d" ]
gap> DigraphAddVertices(D, 0) = D;
true
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 2, 3);
<mutable digraph with 5 vertices, 12 edges>
gap> new := DigraphAddVertices(D, 4);
<mutable digraph with 9 vertices, 12 edges>
gap> D = new;
true

3.3-17 DigraphAddEdge

If edge is a pair of vertices of digraph, or src and ran are vertices of digraph, then this operation returns a digraph constructed from digraph by adding a new edge with source edge[1] [src] and range edge[2] [ran].

If digraph belongs to IsMutableDigraph (3.1-2), then the edge is added directly to digraph. If digraph belongs to IsImmutableDigraph (3.1-3), then an immutable copy of digraph with the additional edge is returned.

gap> D1 := Digraph([[2], [3], []]);
<immutable digraph with 3 vertices, 2 edges>
gap> DigraphEdges(D1);
[ [ 1, 2 ], [ 2, 3 ] ]
gap> D2 := DigraphAddEdge(D1, [3, 1]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphEdges(D2);
[ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ] ]
gap> D3 := DigraphAddEdge(D2, [2, 3]);
<immutable multidigraph with 3 vertices, 4 edges>
gap> DigraphEdges(D3);
[ [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 3, 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 4);
<mutable digraph with 4 vertices, 4 edges>
gap> new := DigraphAddEdge(D, [1, 3]);
<mutable digraph with 4 vertices, 5 edges>
gap> DigraphEdges(new);
[ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ], [ 3, 4 ], [ 4, 1 ] ]
gap> D = new;
true

3.3-18 DigraphAddEdgeOrbit

This operation returns a new digraph with the same vertices and edges as digraph and with additional edges consisting of the orbit of the edge edge under the action of the DigraphGroup (7.2-10) of digraph. If edge is already an edge in digraph, then digraph is returned unchanged. The argument digraph must be an immutable digraph.

gap> gr1 := CayleyDigraph(DihedralGroup(8));
<immutable digraph with 8 vertices, 24 edges>
gap> gr2 := DigraphAddEdgeOrbit(gr1, [1, 8]);
<immutable digraph with 8 vertices, 32 edges>
gap> DigraphEdges(gr1);
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 5 ], [ 2, 6 ], 
  [ 3, 8 ], [ 3, 4 ], [ 3, 7 ], [ 4, 6 ], [ 4, 7 ], [ 4, 1 ], 
  [ 5, 7 ], [ 5, 6 ], [ 5, 8 ], [ 6, 4 ], [ 6, 8 ], [ 6, 2 ], 
  [ 7, 5 ], [ 7, 1 ], [ 7, 3 ], [ 8, 3 ], [ 8, 2 ], [ 8, 5 ] ]
gap> DigraphEdges(gr2);
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 8 ], [ 2, 1 ], [ 2, 5 ], 
  [ 2, 6 ], [ 2, 7 ], [ 3, 8 ], [ 3, 4 ], [ 3, 7 ], [ 3, 6 ], 
  [ 4, 6 ], [ 4, 7 ], [ 4, 1 ], [ 4, 5 ], [ 5, 7 ], [ 5, 6 ], 
  [ 5, 8 ], [ 5, 4 ], [ 6, 4 ], [ 6, 8 ], [ 6, 2 ], [ 6, 3 ], 
  [ 7, 5 ], [ 7, 1 ], [ 7, 3 ], [ 7, 2 ], [ 8, 3 ], [ 8, 2 ], 
  [ 8, 5 ], [ 8, 1 ] ]
gap> gr3 := DigraphRemoveEdgeOrbit(gr2, [1, 8]);
<immutable digraph with 8 vertices, 24 edges>
gap> gr3 = gr1;
true

3.3-19 DigraphAddEdges

If edges is a (possibly empty) list of pairs of vertices of digraph, then this operation returns a digraph constructed from digraph by adding the edges specified by edges. More precisely, for every edge in edges, a new edge will be added with source edge[1] and range edges[2].

If an edge is included in edges with multiplicity k, then it will be added k times. If digraph belongs to IsMutableDigraph (3.1-2), then the edges are added directly to digraph. If digraph belongs to IsImmutableDigraph (3.1-3), then the result is returned as an immutable digraph.

gap> func := function(n)
>  local source, range, i;
>  source := [];
>  range  := [];
>  for i in [1 .. n - 2] do
>    Add(source, i);
>    Add(range, i + 1);
>  od;
>  return Digraph(n, source, range);
> end;;
gap> D := func(1024);
<immutable digraph with 1024 vertices, 1022 edges>
gap> new := DigraphAddEdges(D,
> [[1023, 1024], [1, 1024], [1023, 1024], [1024, 1]]);
<immutable multidigraph with 1024 vertices, 1026 edges>
gap> D = new;
false
gap> D2 := DigraphMutableCopy(func(1024));
<mutable digraph with 1024 vertices, 1022 edges>
gap> new := DigraphAddEdges(D2,
> [[1023, 1024], [1, 1024], [1023, 1024], [1024, 1]]);
<mutable multidigraph with 1024 vertices, 1026 edges>
gap> D2 = new;
true

3.3-20 DigraphRemoveVertex

If v is a vertex of digraph, then this operation returns a digraph constructed from digraph by removing vertex v, along with any edge whose source or range vertex is v.

If digraph has n vertices, then the vertices of the returned digraph are [1..n-1], but the original labels can be accessed via DigraphVertexLabels (5.1-12).

If digraph belongs to IsMutableDigraph (3.1-2), then the vertex is removed directly from digraph. If digraph belongs to IsImmutableDigraph (3.1-3), an immutable copy of digraph without the vertex is returned.

gap> D := Digraph(["a", "b", "c"],
>                  ["a", "a", "b", "c", "c"],
>                  ["b", "c", "a", "a", "c"]);
<immutable digraph with 3 vertices, 5 edges>
gap> DigraphVertexLabels(D);
[ "a", "b", "c" ]
gap> DigraphEdges(D);
[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 3, 1 ], [ 3, 3 ] ]
gap> new := DigraphRemoveVertex(D, 2);
<immutable digraph with 2 vertices, 3 edges>
gap> DigraphVertexLabels(new);
[ "a", "c" ]
gap> D := CycleDigraph(IsMutableDigraph, 5);
<mutable digraph with 5 vertices, 5 edges>
gap> new := DigraphRemoveVertex(D, 1);
<mutable digraph with 4 vertices, 3 edges>
gap> DigraphVertexLabels(D);
[ 2, 3, 4, 5 ]
gap> D = new;
true

3.3-21 DigraphRemoveVertices

If verts is a (possibly empty) duplicate-free list of vertices of digraph, then this operation returns a digraph constructed from digraph by removing every vertex in verts, along with any edge whose source or range vertex is in verts.

If digraph has n vertices, then the vertices of the new digraph are [1 .. n-Length(verts)], but the original labels can be accessed via DigraphVertexLabels (5.1-12).

If digraph belongs to IsMutableDigraph (3.1-2), then the vertices are removed directly from digraph. If digraph belongs to IsImmutableDigraph (3.1-3), an immutable copy of digraph without the vertices is returned.

gap> D := Digraph([[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]);
<immutable digraph with 5 vertices, 11 edges>
gap> SetDigraphVertexLabels(D, ["a", "b", "c", "d", "e"]);
gap> new := DigraphRemoveVertices(D, [2, 4]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphVertexLabels(new);
[ "a", "c", "e" ]
gap> D := CycleDigraph(IsMutableDigraph, 5);
<mutable digraph with 5 vertices, 5 edges>
gap> new := DigraphRemoveVertices(D, [1, 3]);
<mutable digraph with 3 vertices, 1 edge>
gap> DigraphVertexLabels(D);
[ 2, 4, 5 ]
gap> D = new;
true

3.3-22 DigraphRemoveEdge

If digraph is a digraph with no multiple edges and edge is a pair of vertices of digraph, or src and ran are vertices of digraph, then this operation returns a digraph constructed from digraph by removing the edge specified by edge or [src, ran].

If digraph belongs to IsMutableDigraph (3.1-2), then the edge is removed directly from digraph. If digraph belongs to IsImmutableDigraph (3.1-3), an immutable copy of digraph without the edge is returned.

Note that if digraph belongs to IsImmutableDigraph (3.1-3), then a new copy of digraph will be returned even if edge or [src, ran] does not define an edge of digraph.

gap> D := CycleDigraph(250000);
<immutable cycle digraph with 250000 vertices>
gap> D := DigraphRemoveEdge(D, [250000, 1]);
<immutable digraph with 250000 vertices, 249999 edges>
gap> new := DigraphRemoveEdge(D, [25000, 2]);;
gap> new = D;
true
gap> IsIdenticalObj(new, D);
false
gap> D := DigraphMutableCopy(D);;
gap> new := DigraphRemoveEdge(D, 2500, 2);;
gap> IsIdenticalObj(new, D);
true

3.3-23 DigraphRemoveEdgeOrbit

This operation returns a new digraph with the same vertices as digraph and with the orbit of the edge edge (under the action of the DigraphGroup (7.2-10) of digraph) removed. If edge is not an edge in digraph, then digraph is returned unchanged. The argument digraph must be an immutable digraph.

gap> gr1 := CayleyDigraph(DihedralGroup(8));
<immutable digraph with 8 vertices, 24 edges>
gap> gr2 := DigraphAddEdgeOrbit(gr1, [1, 8]);
<immutable digraph with 8 vertices, 32 edges>
gap> DigraphEdges(gr1);
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 5 ], [ 2, 6 ], 
  [ 3, 8 ], [ 3, 4 ], [ 3, 7 ], [ 4, 6 ], [ 4, 7 ], [ 4, 1 ], 
  [ 5, 7 ], [ 5, 6 ], [ 5, 8 ], [ 6, 4 ], [ 6, 8 ], [ 6, 2 ], 
  [ 7, 5 ], [ 7, 1 ], [ 7, 3 ], [ 8, 3 ], [ 8, 2 ], [ 8, 5 ] ]
gap> DigraphEdges(gr2);
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 8 ], [ 2, 1 ], [ 2, 5 ], 
  [ 2, 6 ], [ 2, 7 ], [ 3, 8 ], [ 3, 4 ], [ 3, 7 ], [ 3, 6 ], 
  [ 4, 6 ], [ 4, 7 ], [ 4, 1 ], [ 4, 5 ], [ 5, 7 ], [ 5, 6 ], 
  [ 5, 8 ], [ 5, 4 ], [ 6, 4 ], [ 6, 8 ], [ 6, 2 ], [ 6, 3 ], 
  [ 7, 5 ], [ 7, 1 ], [ 7, 3 ], [ 7, 2 ], [ 8, 3 ], [ 8, 2 ], 
  [ 8, 5 ], [ 8, 1 ] ]
gap> gr3 := DigraphRemoveEdgeOrbit(gr2, [1, 8]);
<immutable digraph with 8 vertices, 24 edges>
gap> gr3 = gr1;
true

3.3-24 DigraphRemoveEdges

then this operation returns a digraph constructed from digraph by removing all of the edges specified by edges (see DigraphRemoveEdge (3.3-22)).

If digraph belongs to IsMutableDigraph (3.1-2), then the edge is removed directly from digraph. If digraph belongs to IsImmutableDigraph (3.1-3), the edge is removed from an immutable copy of digraph and this new digraph is returned.

Note that if edges is empty, then this operation will always return digraph rather than a copy. Also, if any element of edges is invalid (i.e. does not define an edge of digraph) then that element will simply be ignored.

gap> D := CycleDigraph(250000);
<immutable cycle digraph with 250000 vertices>
gap> D := DigraphRemoveEdges(D, [[250000, 1]]);
<immutable digraph with 250000 vertices, 249999 edges>
gap> D := DigraphMutableCopy(D);
<mutable digraph with 250000 vertices, 249999 edges>
gap> new := DigraphRemoveEdges(D, [[1, 2], [2, 3], [3, 100]]);
<mutable digraph with 250000 vertices, 249997 edges>
gap> new = D;
true

3.3-25 DigraphRemoveLoops

If digraph is a digraph, then this operation returns a digraph constructed from digraph by removing every loop. A loop is an edge with equal source and range.

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the loops are removed from the mutable digraph digraph in-place.

gap> D := Digraph([[1, 2, 4], [1, 4], [3, 4], [1, 4, 5], [1, 5]]);
<immutable digraph with 5 vertices, 12 edges>
gap> DigraphRemoveLoops(D);
<immutable digraph with 5 vertices, 8 edges>
gap> D := Digraph(IsMutableDigraph, [[1, 2], [1]]);
<mutable digraph with 2 vertices, 3 edges>
gap> DigraphRemoveLoops(D);
<mutable digraph with 2 vertices, 2 edges>
gap> D;
<mutable digraph with 2 vertices, 2 edges>

3.3-26 DigraphRemoveAllMultipleEdges

If digraph is a digraph, then this operation returns a digraph constructed from digraph by removing all multiple edges. The result is the largest subdigraph of digraph which does not contain multiple edges.

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the multiple edges of the mutable digraph digraph are removed in-place.

gap> D1 := Digraph([[1, 2, 3, 2], [1, 1, 3], [2, 2, 2]]);
<immutable multidigraph with 3 vertices, 10 edges>
gap> D2 := DigraphRemoveAllMultipleEdges(D1);
<immutable digraph with 3 vertices, 6 edges>
gap> OutNeighbours(D2);
[ [ 1, 2, 3 ], [ 1, 3 ], [ 2 ] ]
gap> D := Digraph(IsMutableDigraph, [[2, 2], [1]]);
<mutable multidigraph with 2 vertices, 3 edges>
gap> DigraphRemoveAllMultipleEdges(D);
<mutable digraph with 2 vertices, 2 edges>
gap> D;
<mutable digraph with 2 vertices, 2 edges>

3.3-27 DigraphContractEdge

If edge is a pair of vertices of digraph, or src and ran are vertices of digraph, where ran <> src, then then this operation merges the two vertices of the edge given into one. Edges incident to src and ran will now be incident to v, the new vertex, with their direction preserved.

A new digraph constructed from digraph is returned, unless digraph belongs to IsMutableDigraph (3.1-2); in this case changes are made directly to digraph, which is then returned. The digraph must not belong to IsMultiDigraph (6.2-11).

Assigned vertex labels for src and ran are combined into a list, and assigned to the new vertex v.

If an edge [src, src] or [ran, ran] exists, a singular edge [v, v] is created. If edge [ran, src] exists, this is also removed.

gap> D := DigraphByEdges([[1, 2], [2, 1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> D2 := DigraphContractEdge(D, 1, 2);
<immutable empty digraph with 1 vertex>
gap> DigraphEdges(D2);
[  ]
gap> D := DigraphByEdges(IsMutableDigraph, [[1, 2], [2, 3], [3, 4]]);
<mutable digraph with 4 vertices, 3 edges>
gap> DigraphVertexLabels(D);;  # setting vertex labels
gap> DigraphContractEdge(D, [2, 3]);
<mutable digraph with 3 vertices, 2 edges>
gap> DigraphEdges(D);
[ [ 1, 3 ], [ 3, 2 ] ]
gap> DigraphVertexLabels(D);
[ 1, 4, [ 2, 3 ] ]

3.3-28 DigraphReverseEdges

If digraph is a digraph without multiple edges, and edges is a list of pairs of vertices of digraph (the entries of each pair corresponding to the source and the range of an edge, respectively), then DigraphReverseEdges returns a digraph constructed from digraph by reversing the orientation of every edge specified by edges. If only one edge is to be reversed, then DigraphReverseEdge can be used instead. In this case, the second argument should just be a single vertex-pair, or the second and third arguments should be the source and range of an edge respectively.

Note that even though digraph cannot have multiple edges, the output may have multiple edges.

If digraph belongs to IsMutableDigraph (3.1-2), then the edges are reversed in digraph. If digraph belongs to IsImmutableDigraph (3.1-3), an immutable copy of digraph with the specified edges reversed is returned.

gap> D := DigraphFromDiSparse6String(".Tg?i@s?t_e?_qEsC");
<immutable digraph with 21 vertices, 8 edges>
gap> DigraphEdges(D);
[ [ 1, 2 ], [ 1, 7 ], [ 1, 8 ], [ 5, 21 ], [ 7, 19 ], [ 9, 1 ], 
  [ 11, 2 ], [ 21, 1 ] ]
gap> new := DigraphReverseEdge(D, [7, 19]);
<immutable digraph with 21 vertices, 8 edges>
gap> DigraphEdges(new);
[ [ 1, 2 ], [ 1, 7 ], [ 1, 8 ], [ 5, 21 ], [ 9, 1 ], [ 11, 2 ], 
  [ 19, 7 ], [ 21, 1 ] ]
gap> D2 := DigraphMutableCopy(new);;
gap> new := DigraphReverseEdges(D2, [[19, 7]]);;
gap> D2 = new;
true
gap> D = new;
true

3.3-29 DigraphDisjointUnion

In the first form, if D1, D2, etc. are digraphs, then DigraphDisjointUnion returns their disjoint union. In the second form, if list is a non-empty list of digraphs, then DigraphDisjointUnion returns the disjoint union of the digraphs contained in the list.

For a disjoint union of digraphs, the vertex set is the disjoint union of the vertex sets, and the edge list is the disjoint union of the edge lists.

More specifically, for a collection of digraphs D1, D2, ..., the disjoint union with have DigraphNrVertices(D1) + DigraphNrVertices(D2) + ... vertices. The edges of D1 will remain unchanged, whilst the edges of the ith digraph, D[i], will be changed so that they belong to the vertices of the disjoint union corresponding to D[i]. In particular, the edges of D[i] will have their source and range increased by DigraphNrVertices(D1) + ... + DigraphNrVertices(D[i-1]).

If the first digraph D1 [list[1]] belongs to IsMutableDigraph (3.1-2), then D1 [list[1]] is modified in place to contain the appropriate vertices and edges. If digraph belongs to IsImmutableDigraph (3.1-3), a new immutable digraph containing the appropriate vertices and edges is returned.

gap> D1 := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> OutNeighbours(D1);
[ [ 2 ], [ 3 ], [ 1 ] ]
gap> D2 := CompleteDigraph(3);
<immutable complete digraph with 3 vertices>
gap> OutNeighbours(D2);
[ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ]
gap> union := DigraphDisjointUnion(D1, D2);
<immutable digraph with 6 vertices, 9 edges>
gap> OutNeighbours(union);
[ [ 2 ], [ 3 ], [ 1 ], [ 5, 6 ], [ 4, 6 ], [ 4, 5 ] ]

3.3-30 DigraphEdgeUnion

In the first form, if D1, D2, etc. are digraphs, then DigraphEdgeUnion returns their edge union. In the second form, if list is a non-empty list of digraphs, then DigraphEdgeUnion returns the edge union of the digraphs contained in the list.

The vertex set of the edge union of a collection of digraphs is the union of the vertex sets, whilst the edge list of the edge union is the concatenation of the edge lists. The number of vertices of the edge union is equal to the maximum number of vertices of one of the digraphs, whilst the number of edges of the edge union will equal the sum of the number of edges of each digraph.

gap> D := CycleDigraph(10);
<immutable cycle digraph with 10 vertices>
gap> DigraphEdgeUnion(D, D);
<immutable multidigraph with 10 vertices, 20 edges>
gap> D1 := Digraph([[2], [1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> D2 := Digraph([[2, 3], [2], [1]]);
<immutable digraph with 3 vertices, 4 edges>
gap> union := DigraphEdgeUnion(D1, D2);
<immutable multidigraph with 3 vertices, 6 edges>
gap> OutNeighbours(union);
[ [ 2, 2, 3 ], [ 1, 2 ], [ 1 ] ]
gap> union = DigraphByEdges(
> Concatenation(DigraphEdges(D1), DigraphEdges(D2)));
true

3.3-31 DigraphJoin

In the first form, if D1, D2, etc. are digraphs, then DigraphJoin returns their join. In the second form, if list is a non-empty list of digraphs, then DigraphJoin returns the join of the digraphs contained in the list.

The join of a collection of digraphs D1, D2, ... is formed by first taking the DigraphDisjointUnion (3.3-29) of the collection. In the disjoint union, if \(i \neq j\) then there are no edges between vertices corresponding to digraphs D[i] and D[j] in the collection; the join is created by including all such edges.

gap> D := CompleteDigraph(3);
<immutable complete digraph with 3 vertices>
gap> IsCompleteDigraph(DigraphJoin(D, D));
true
gap> D2 := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> DigraphJoin(D, D2);
<immutable digraph with 6 vertices, 27 edges>

3.3-32 DigraphCartesianProduct

In the first form, if gr1, gr2, etc. are digraphs, then DigraphCartesianProduct returns a digraph isomorphic to their Cartesian product.

In the second form, if list is a non-empty list of digraphs, then DigraphCartesianProduct returns a digraph isomorphic to the Cartesian product of the digraphs contained in the list.

Mathematically, the Cartesian product of two digraphs G, H is a digraph with vertex set Cartesian(DigraphVertices(G), DigraphVertices(H)) such that there is an edge from [u, u'] to [v, v'] iff u = v and there is an edge from u' to v' in H or u' = v' and there is an edge from u to v in G.

Due to technical reasons, the digraph D returned by DigraphCartesianProduct has vertex set [1 .. DigraphNrVertices(G)*DigraphNrVertices(H)] instead, and the exact method of encoding pairs of vertices into integers is implementation specific. The original vertex pair can be somewhat regained by using DigraphCartesianProductProjections (3.3-39). In addition, DigraphVertexLabels (5.1-12) are preserved: if vertex pair [u,u'] was encoded as i then the vertex label of i will be the pair of vertex labels of u and u' i.e. DigraphVertexLabel(D,i) = [DigraphVertexLabel(G,u), DigraphVertexLabel(H,u')].

As the Cartesian product is associative, the Cartesian product of a collection of digraphs gr1, gr2, ... is computed in the obvious fashion.

gap> gr := ChainDigraph(4);
<immutable chain digraph with 4 vertices>
gap> gr2 := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> gr3 := DigraphCartesianProduct(gr, gr2);
<immutable digraph with 12 vertices, 21 edges>
gap> IsIsomorphicDigraph(gr3, 
> Digraph([[2, 5], [3, 6], [4, 7], [8], 
>          [6, 9], [7, 10], [8, 11], [12],
>          [10, 1], [11, 2], [12, 3], [4]]));
true

3.3-33 DigraphDirectProduct

In the first form, if gr1, gr2, etc. are digraphs, then DigraphDirectProduct returns a digraph isomorphic to their direct product.

In the second form, if list is a non-empty list of digraphs, then DigraphDirectProduct returns a digraph isomorphic to the direct product of the digraphs contained in the list.

Mathematically, the direct product of two digraphs G, H is a digraph with vertex set Cartesian(DigraphVertices(G), DigraphVertices(H)) such that there is an edge from [u, u'] to [v, v'] iff there is an edge from u to v in G and an edge from u' to v' in H.

Due to technical reasons, the digraph D returned by DigraphDirectProduct has vertex set [1 .. DigraphNrVertices(G)*DigraphNrVertices(H)] instead, and the exact method of encoding pairs of vertices into integers is implementation specific. The original vertex pair can be somewhat regained by using DigraphDirectProductProjections (3.3-40). In addition DigraphVertexLabels (5.1-12) are preserved: if vertex pair [u,u'] was encoded as i then the vertex label of i will be the pair of vertex labels of u and u' i.e. DigraphVertexLabel(D,i) = [DigraphVertexLabel(G,u), DigraphVertexLabel(H,u')].

As the direct product is associative, the direct product of a collection of digraphs gr1, gr2, ... is computed in the obvious fashion.

gap> gr := ChainDigraph(4);
<immutable chain digraph with 4 vertices>
gap> gr2 := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> gr3 := DigraphDirectProduct(gr, gr2);
<immutable digraph with 12 vertices, 9 edges>
gap> IsIsomorphicDigraph(gr3, 
> Digraph([[6], [7], [8], [], 
>          [10], [11], [12], [],
>          [2], [3], [4], []]));
true

3.3-34 ConormalProduct

If D1 and D2 are digraphs without multiple edges, then ConormalProduct calculates the co-normal product digraph (CNPD) of D1 and D2. CNPD has vertex set V1 x V2 where V1 is the vertex set of D1 and V2 is the vertex set of D2 (a vertex [a, b] has label (a - 1) * |V2| + b in the output). There is an edge from [a, b] to [c, d] when at least one of the following two conditions are satisfied:

gap> ConormalProduct(DigraphSymmetricClosure(CycleDigraph(7)),
> DigraphSymmetricClosure(CycleDigraph(4)));
<immutable digraph with 28 vertices, 504 edges>
gap> ConormalProduct(NullDigraph(0), CompleteDigraph(10));
<immutable empty digraph with 0 vertices>

3.3-35 HomomorphicProduct

If D1 and D2 are digraphs without multiple edges, then HomomorphicProduct calculates the homomorphic product digraph (HPD) of D1 and D2. HPD has vertex set V1 x V2 where V1 is the vertex set of D1 and V2 is the vertex set of D2 (a vertex [a, b] has label (a - 1) * |V2| + b in the output). There is an edge from [a, b] to [c, d] when at least one of the following two conditions are satisfied:

gap> HomomorphicProduct(PetersenGraph(),
> DigraphSymmetricClosure(ChainDigraph(4)));
<immutable digraph with 40 vertices, 460 edges>
gap> D1 := Digraph([[2], [1, 3, 4], [2, 5], [2, 5], [3, 4]]);
<immutable digraph with 5 vertices, 10 edges>
gap> D2 := Digraph([[2], [1, 3], [2, 4], [3]]);
<immutable digraph with 4 vertices, 6 edges>
gap> HomomorphicProduct(D1, D2);
<immutable digraph with 20 vertices, 180 edges>

3.3-36 LexicographicProduct

If D1 and D2 are digraphs without multiple edges, then LexicographicProduct calculates the lexicographic product digraph (LPD) of D1 and D2. LPD has vertex set V1 x V2 where V1 is the vertex set of D1 and V2 is the vertex set of D2 (a vertex [a, b] has label (a - 1) * |V2| + b in the output). There is an edge from [a, b] to [c, d] when at least one of the following two conditions are satisfied:

gap> LexicographicProduct(DigraphSymmetricClosure(CycleDigraph(3)),
> DigraphSymmetricClosure(ChainDigraph(2)));
<immutable digraph with 6 vertices, 30 edges>
gap> OutNeighbours(last);
[ [ 2, 3, 4, 5, 6 ], [ 1, 3, 4, 5, 6 ], [ 1, 2, 4, 5, 6 ], 
  [ 1, 2, 3, 5, 6 ], [ 1, 2, 3, 4, 6 ], [ 1, 2, 3, 4, 5 ] ]
gap> LexicographicProduct(NullDigraph(0), CompleteDigraph(10));
<immutable empty digraph with 0 vertices>

3.3-37 ModularProduct

If D1 and D2 are digraphs without multiple edges, then ModularProduct calculates the modular product digraph (MPD) of D1 and D2. MPD has vertex set V1 x V2 where V1 is the vertex set of D1 and V2 is the vertex set of D2 (a vertex [a, b] has label (a - 1) * |V2| + b in the output). There is an edge from [a, b] to [c, d] precisely when the following two conditions are satisfied:

Notably, the complete (with loops) subdigraphs of MPD are precisely the partial isomorphisms from D1 to D2.

gap> ModularProduct(Digraph([[1], [1, 2]]), Digraph([[], [2]]));
<immutable digraph with 4 vertices, 4 edges>
gap> OutNeighbours(last);
[ [ 4 ], [ 2, 3 ], [  ], [ 4 ] ]
gap> ModularProduct(PetersenGraph(),
> DigraphSymmetricClosure(CycleDigraph(5)));
<immutable digraph with 50 vertices, 950 edges>
gap> ModularProduct(NullDigraph(0), CompleteDigraph(10));
<immutable empty digraph with 0 vertices>

3.3-38 StrongProduct

If D1 and D2 are digraphs without multiple edges, then StrongProduct calculates the strong product digraph (SPD) of D1 and D2. SPD has vertex set V1 x V2 where V1 is the vertex set of D1 and V2 is the vertex set of D2 (a vertex [a, b] has label (a - 1) * |V2| + b in the output). There is an edge from [a, b] to [c, d] when at least one of the following three conditions are satisfied:

The SPD of two paths of lengths m and n is also the king's graph for an m by n board.

gap> D1 := Digraph([[2], [1, 3, 4], [2, 5], [2, 5], [3, 4]]);
<immutable digraph with 5 vertices, 10 edges>
gap> D2 := Digraph([[2], [1, 3, 4], [2], [2]]);
<immutable digraph with 4 vertices, 6 edges>
gap> StrongProduct(D1, D2);
<immutable digraph with 20 vertices, 130 edges>
gap> StrongProduct(DigraphSymmetricClosure(ChainDigraph(3)),
> DigraphSymmetricClosure(ChainDigraph(4)));
<immutable digraph with 12 vertices, 58 edges>

3.3-39 DigraphCartesianProductProjections

If digraph is a Cartesian product digraph, digraph = DigraphCartesianProduct(gr_1, gr_2, ... ), then DigraphCartesianProductProjections returns a list proj such that proj[i] is the projection onto the i-th coordinate of the product.

A projection is an idempotent endomorphism of digraph. If gr1, gr2, ... are all loopless digraphs, then the induced subdigraph of digraph on the image of proj[i] is isomorphic to gr_i.

Currently this attribute is only set upon creating an immutable digraph via DigraphCartesianProduct and there is no way of calculating it for other digraphs.

gap> D := DigraphCartesianProduct(ChainDigraph(3), CycleDigraph(4),
> Digraph([[2], [2]]));;
gap> HasDigraphCartesianProductProjections(D);
true
gap> proj := DigraphCartesianProductProjections(D);; Length(proj);
3
gap> IsIdempotent(proj[2]);
true
gap> RankOfTransformation(proj[3]);
2
gap> S := ImageSetOfTransformation(proj[2]);;
gap> IsIsomorphicDigraph(CycleDigraph(4), InducedSubdigraph(D, S));
true

3.3-40 DigraphDirectProductProjections

If digraph is a direct product digraph, digraph = DigraphDirectProduct(gr_1, gr_2, ... ), then DigraphDirectProductProjections returns a list proj such that proj[i] is the projection onto the i-th coordinate of the product.

A projection is an idempotent endomorphism of digraph. If gr1, gr2, ... are all loopless digraphs, then the image of digraph under proj[i] is isomorphic to gr_i.

Currently this attribute is only set upon creating an immutable digraph via DigraphDirectProduct and there is no way of calculating it for other digraphs.

gap> D := DigraphDirectProduct(ChainDigraph(3), CycleDigraph(4),
> Digraph([[2], [2]]));;
gap> HasDigraphDirectProductProjections(D);
true
gap> proj := DigraphDirectProductProjections(D);; Length(proj);
3
gap> IsIdempotent(proj[2]);
true
gap> RankOfTransformation(proj[3]);
2
gap> P := DigraphRemoveAllMultipleEdges(
> ReducedDigraph(OnDigraphs(D, proj[2])));; 
gap> IsIsomorphicDigraph(CycleDigraph(4), P);
true

3.3-41 LineDigraph

Given a digraph digraph, the operation returns the digraph obtained by associating a vertex with each edge of digraph, and creating an edge from a vertex v to a vertex u if and only if the terminal vertex of the edge associated with v is the start vertex of the edge associated with u.

Note that the returned digraph is always a new immutable digraph, and the argument digraph is never modified.

gap> LineDigraph(CompleteDigraph(3));
<immutable digraph with 6 vertices, 12 edges>
gap> LineDigraph(ChainDigraph(3));
<immutable digraph with 2 vertices, 1 edge>

3.3-42 LineUndirectedDigraph

Given a symmetric digraph digraph, the operation returns the symmetric digraph obtained by associating a vertex with each edge of digraph, ignoring directions and multiplicities, and adding an edge between two vertices if and only if the corresponding edges have a vertex in common.

Note that the returned digraph is always a new immutable digraph, and the argument digraph is never modified.

gap> LineUndirectedDigraph(CompleteDigraph(3));
<immutable digraph with 3 vertices, 6 edges>
gap> LineUndirectedDigraph(DigraphSymmetricClosure(ChainDigraph(3)));
<immutable digraph with 2 vertices, 2 edges>

3.3-43 DoubleDigraph

Let digraph be a digraph with vertex set V. This function returns the double digraph of digraph. The vertex set of the double digraph is the original vertex set together with a duplicate. The edges are [u_1, v_2] and [u_2, v_1] if and only if [u, v] is an edge in digraph, together with the original edges and their duplicates.

If digraph is mutable, then digraph is modified in-place. If digraph is immutable, then a new immutable digraph constructed as described above is returned.

gap> gamma := Digraph([[2], [3], [1]]);
<immutable digraph with 3 vertices, 3 edges>
gap> DoubleDigraph(gamma);
<immutable digraph with 6 vertices, 12 edges>

3.3-44 BipartiteDoubleDigraph

Let digraph be a digraph with vertex set V. This function returns the bipartite double digraph of digraph. The vertex set of the double digraph is the original vertex set together with a duplicate. The edges are [u_1, v_2] and [u_2, v_1] if and only if [u, v] is an edge in digraph. The resulting graph is bipartite, since the original edges are not included in the resulting digraph.

If digraph is mutable, then digraph is modified in-place. If digraph is immutable, then a new immutable digraph constructed as described above is returned.

gap> gamma := Digraph([[2], [3], [1]]);
<immutable digraph with 3 vertices, 3 edges>
gap> BipartiteDoubleDigraph(gamma);
<immutable digraph with 6 vertices, 6 edges>

3.3-45 DigraphAddAllLoops

For a digraph digraph this operation returns a new digraph constructed from digraph, such that a loop is added for every vertex which did not have a loop in digraph.

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the loops are added to the loopless vertices of the mutable digraph digraph in-place.

gap> D := EmptyDigraph(13);
<immutable empty digraph with 13 vertices>
gap> D := DigraphAddAllLoops(D);
<immutable reflexive digraph with 13 vertices, 13 edges>
gap> OutNeighbours(D);
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ], [ 8 ], [ 9 ], 
  [ 10 ], [ 11 ], [ 12 ], [ 13 ] ]
gap> D := Digraph([[1, 2, 3], [1, 3], [1]]);
<immutable digraph with 3 vertices, 6 edges>
gap> D := DigraphAddAllLoops(D);
<immutable reflexive digraph with 3 vertices, 8 edges>
gap> OutNeighbours(D);
[ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 1, 3 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphAddAllLoops(D);
<mutable digraph with 3 vertices, 6 edges>
gap> D;
<mutable digraph with 3 vertices, 6 edges>

3.3-46 DistanceDigraph

The first argument is a digraph, the second argument is a non-negative integer or a list of positive integers. This operation returns a digraph on the same set of vertices as digraph, with two vertices being adjacent if and only if the distance between them in digraph equals i or is a number in list. See DigraphShortestDistance (5.4-2).

If digraph is mutable, then digraph is modified in-place. If digraph is immutable, then a new immutable digraph constructed as described above is returned.

gap> digraph := DigraphFromSparse6String(
> ":]n?AL`BC_DEbEF`GIaGHdIJeGKcKL_@McDHfILaBJfHMjKM");
<immutable symmetric digraph with 30 vertices, 90 edges>
gap> DistanceDigraph(digraph, 1);
<immutable digraph with 30 vertices, 90 edges>
gap> DistanceDigraph(digraph, [1, 2]);
<immutable digraph with 30 vertices, 270 edges>

3.3-47 DigraphClosure

Given a symmetric loopless digraph with no multiple edges digraph, the k-closure of digraph is defined to be the unique smallest symmetric loopless digraph C with no multiple edges on the vertices of digraph that contains all the edges of digraph and satisfies the property that the sum of the degrees of every two non-adjacenct vertices in C is less than k. See IsSymmetricDigraph (6.2-14), DigraphHasLoops (6.2-1), IsMultiDigraph (6.2-11), and OutDegreeOfVertex (5.2-10).

gap> D := CompleteDigraph(6);
<immutable complete digraph with 6 vertices>
gap> D := DigraphRemoveEdges(D, [[1, 2], [2, 1]]);
<immutable digraph with 6 vertices, 28 edges>
gap> closure := DigraphClosure(D, 6);
<immutable digraph with 6 vertices, 30 edges>
gap> IsCompleteDigraph(closure);
true

3.3-48 DigraphMycielskian

If digraph is a symmetric digraph, then DigraphMycielskian returns the Mycielskian of digraph.

The Mycielskian of a symmetric digraph is a larger symmetric digraph constructed from it, which has a larger chromatic number. For further information, see https://en.wikipedia.org/wiki/Mycielskian.

If digraph is immutable, then a new immutable digraph is returned. Otherwise, the mutable digraph digraph is changed in-place into its Mycielskian.

gap> D := CycleDigraph(2);
<immutable cycle digraph with 2 vertices>
gap> ChromaticNumber(D);
2
gap> D := DigraphMycielskian(D);
<immutable digraph with 5 vertices, 10 edges>
gap> ChromaticNumber(D);
3
gap> D := DigraphMycielskian(D);
<immutable digraph with 11 vertices, 40 edges>
gap> ChromaticNumber(D);
4
gap> D := CompleteBipartiteDigraph(IsMutable, 2, 3);
<mutable digraph with 5 vertices, 12 edges>
gap> DigraphMycielskian(D);
<mutable digraph with 11 vertices, 46 edges>
gap> D;
<mutable digraph with 11 vertices, 46 edges>

3.4 Random digraphs

3.4-1 RandomDigraph

The other implemented filters are as follows: IsConnectedDigraph (6.6-3), IsSymmetricDigraph (6.2-14), IsAcyclicDigraph (6.6-1), IsEulerianDigraph (6.6-10), IsHamiltonianDigraph (6.6-11).

For IsConnectedDigraph (6.6-3), a random tree is first created independent of the value of p, guaranteeing connectivity (with \(\textit{n}-1\) edges), and then edges are added between the remaining pairs of vertices with probability approximately p.

For IsHamiltonianDigraph (6.6-11), a random Hamiltonian cycle is first created independent of the value of p (with n edges), and then edges are added between the remaining pairs of vertices with probability approximately p.

For IsEulerianDigraph (6.6-10), a random Eulerian cycle is created where p influences how long the cycle will be. The cycle grows by randomly considering edges that extend the cycle, and adding an edge with probability approximately p. The cycle stops when we get back to the start vertex and have no more edges left to consider from it that extend the cycle further (any possible edge from the start vertex has either been added to the cycle, or rejected, leaving no more edges to consider). Thus \(\textit{p} = 1\) does not necessarily guarantee a complete digraph. Instead, it guarantees that all edges considered up to the point where the cycle stops, are added.

For IsAcyclicDigraph (6.6-1) and IsSymmetricDigraph (6.2-14), edges are added between any pairs of vertices with probability approximately p.

If n is a positive integer, then this function returns a random digraph with n vertices and without multiple edges. The result may or may not have loops. If using IsAcyclicDigraph (6.6-1), the resulting graph will not have any loops by definition.

If the optional second argument p is a float with value \(0 \leq \) p \( \leq 1\), then an edge will exist between each pair of vertices with probability approximately p. If p is not specified, then a random probability will be assumed (chosen with uniform probability).

gap> RandomDigraph(1000);
<immutable digraph with 1000 vertices, 364444 edges>
gap> RandomDigraph(10000, 0.023);
<immutable digraph with 10000 vertices, 2300438 edges>
gap> RandomDigraph(IsMutableDigraph, 1000, 1 / 2);
<mutable digraph with 1000 vertices, 499739 edges>
gap> RandomDigraph(IsConnectedDigraph, 1000, 0.75);
<immutable digraph with 1000 vertices, 750265 edges>
gap> RandomDigraph(IsSymmetricDigraph, 1000);
<immutable digraph with 1000 vertices, 329690 edges>
gap> RandomDigraph(IsAcyclicDigraph, 1000, 0.25);
<immutable digraph with 1000 vertices, 125070 edges>
gap> RandomDigraph(IsHamiltonianDigraph, 1000, 0.5);
<immutable digraph with 1000 vertices, 500327 edges>
gap> RandomDigraph(IsEulerianDigraph, 1000, 0.5);
<immutable digraph with 1000 vertices, 433869 edges>

3.4-2 RandomMultiDigraph

If n is a positive integer, then this function returns a random digraph with n vertices. If the optional second argument m is a positive integer, then the digraph will have m edges. If m is not specified, then the number of edges will be chosen randomly (with uniform probability) from the range [1 .. \({n \choose 2}\)].

The method used by this function chooses each edge from the set of all possible edges with uniform probability. No effort is made to avoid creating multiple edges, so it is possible (but not guaranteed) that the result will have multiple edges. The result may or may not have loops.

gap> RandomMultiDigraph(1000);
<immutable multidigraph with 1000 vertices, 216659 edges>
gap> RandomMultiDigraph(1000, 950);
<immutable multidigraph with 1000 vertices, 950 edges>

3.4-3 RandomTournament

If n is a non-negative integer, this function returns a random tournament with n vertices. See IsTournament (6.2-15).

gap> RandomTournament(10);
<immutable tournament with 10 vertices>
gap> RandomTournament(IsMutableDigraph, 10);
<mutable digraph with 1000 vertices, 500601 edges>

3.4-4 RandomLattice

If n is a positive integer, this function return a random lattice with m vertices, where it is guaranteed that m is between n and 2 * n. See IsLatticeDigraph (6.4-3).

gap> RandomLattice(10);
<immutable lattice digraph with 10 vertices, 39 edges>
gap> RandomLattice(IsMutableDigraph, 10);
<mutable digraph with 12 vertices, 52 edges>

3.5 Standard examples

3.5-1 AndrasfaiGraph

If n is an integer greater than 0, then this operation returns the nth Andrasfai graph. The Andrasfai graph is a circulant graph with 3n - 1 vertices. The indices of the Andrasfai graph are given by the numbers between 1 and 3n - 1 that are congruent to 1 mod 3 (that is, for each index \(j\), vertex \(i\) is adjacent to the \(i + j\)th and \(i - j\) vertices). The graph has 6(3n - 1) edges. The graph is triangle free.

As a circulant graph, the Andrasfai graph is biconnected, cyclic, Hamiltonian, regular, and vertex transitive.

gap> D := AndrasfaiGraph(4);
<immutable Hamiltonian biconnected vertex-transitive symmetric digraph\
 with 11 vertices, 44 edges>
gap> IsBiconnectedDigraph(D);
true
gap> IsIsomorphicDigraph(D, CirculantGraph(11, [1, 4, 7, 10]));
true

3.5-2 BananaTree

If n and k are positive integers with k greater than \(1\), then this operation returns the banana tree with parameters n and k, as defined below.

"An (n,k)-banana tree, as defined by Chen et al. (1997), is a graph obtained by connecting one leaf of each of n copies of an k-star graph with a single root vertex that is distinct from all the stars."

Specifically, in the resulting digraph, vertex 1 is the 'root', and for each m in [1 .. k], the mth star is on the vertices [((m - 1) * n) + 2 .. (m * n) + 1], with the first of these being the 'centre' of the star, and the second being the 'leaf' adjacent 1.

gap> D := BananaTree(2, 4);
<immutable undirected tree digraph with 9 vertices>
gap> D := BananaTree(3, 3);
<immutable undirected tree digraph with 10 vertices>
gap> D := BananaTree(5, 2);
<immutable undirected tree digraph with 11 vertices>
gap> D := BananaTree(3, 4);
<immutable undirected tree digraph with 13 vertices>

3.5-3 BinaryTree

This function returns a binary tree of depth m with 2 ^ m - 1 vertices. All edges are directed towards the root of the tree, which is vertex 1.

Note that BinaryTree(m) is the induced subdigraph of BinaryTree(m+1) on the vertices [1..2^(m-1)].

gap> BinaryTree(1);
<immutable empty digraph with 1 vertex>
gap> BinaryTree(8);
<immutable digraph with 255 vertices, 254 edges>
gap> BinaryTree(IsMutableDigraph, 8);
<mutable digraph with 255 vertices, 254 edges>

3.5-4 BinomialTreeGraph

If n is a positive integer then this operation returns the nth binomial tree graph. The binomial tree graph has n vertices and n-1 undirected edges. The vertices of the binomial tree graph are the numbers from 1 to n in binary representation, with a vertex v having as a direct parent the vertex with binary representation the same as v but with the lowest 1-bit cleared. For example, the vertex \(011\) has parent \(010\), and the vertex \(010\) has parent \(000\).

gap> D := BinomialTreeGraph(9);
<immutable undirected tree digraph with 9 vertices>

3.5-5 BishopsGraph

If m and n are positive integers, then this operation returns the bishop's graph of an m by n chessboard, as a symmetric digraph.

A bishop's graph represents all possible moves of the bishop chess piece across a chessboard. An m by n chessboard is a grid of m columns ("files") and n rows ("ranks") that intersect in squares. Orthogonally adjacent squares are alternately colored light and dark, with the square in the first rank and file being dark.

The m * n vertices of the bishop's graph can be placed onto the m * n squares of an m by n chessboard, such that two vertices are adjacent in the digraph if and only if a bishop can move between the corresponding squares in a single turn. A legal bishop's move is defined as any move which moves the bishop piece to a diagonally adjacent square or to a square which can be reached through a series of diagonally adjacent squares, with all of these small moves being in the same direction.

The chosen correspondence between vertices and chess squares is given by DigraphVertexLabels (5.1-12). In more detail, the vertices of the digraph are labelled by elements of the Cartesian product [1..m] x [1..n], where the first entry indexes the column (file) of the square in the chessboard, and the second entry indexes the row (rank) of the square. (Note that the files are traditionally indexed by the lowercase letters of the alphabet). The vertices are sorted in ascending order, first by row (second component) and then column (first component). If the optional second argument color is present, then this should be one of the strings "dark", "light", or "both". The default is "both". A bishop on a light square can only move to light squares, and a bishop on a dark square can only move to dark squares. This optional argument controls which bishops are represented in the resulting digraph. If color is "both", then the resulting digraph will show all the vertices of an m by n chessboard, and will be disconnected (unless m = n = 1). Otherwise, BishopsGraph returns the induced subdigraph of this on the vertices that correspond to either the dark squares or the light squares, according to the value of color.

gap> BishopsGraph(8, 8);
<immutable symmetric digraph with 64 vertices, 560 edges>
gap> D := BishopsGraph("dark", 3, 5);
<immutable connected symmetric digraph with 8 vertices, 24 edges>
gap> IsConnectedDigraph(D);       
true
gap> BishopsGraph("light", 4, 4);
<immutable connected symmetric digraph with 8 vertices, 28 edges>
gap> D := BishopsGraph("both", 1, 5);
<immutable empty digraph with 5 vertices>

3.5-6 BondyGraph

If n is a non-negative integer then this operation returns the nth Bondy graph. The Bondy graphs are a family of hypohamiltonian graphs: a graph which is not Hamiltonian itself but the removal of any vertex produces a Hamiltonian graph. The Bondy graphs are the (3(2n + 1) + 2, 2)-th Generalised Petersen graphs, and have 12n + 10 vertices and 15 + 18n undirected edges.

gap> D := BondyGraph(1);
<immutable symmetric digraph with 22 vertices, 66 edges>
gap> IsHamiltonianDigraph(D);
false
gap> G := List([1 .. 22], x -> DigraphRemoveVertex(D, x));;
gap> ForAll(G, IsHamiltonianDigraph);
true

3.5-7 BookGraph

The book graph is the Cartesian product of a complete digraph with two vertices (as the "book spine") and the \(\textit{m}+1\) star graph (as the "pages"). For more details on the book graph please refer to https://mathworld.wolfram.com/BookGraph.html.

See DigraphCartesianProduct (3.3-32), CompleteDigraph (3.5-11), and StarGraph (3.5-43).

gap> BookGraph(1);
<immutable bipartite symmetric digraph with bicomponent sizes 2 and 2>
gap> BookGraph(2);
<immutable bipartite symmetric digraph with bicomponent sizes 3 and 3>
gap> BookGraph(IsMutable, 12);
<mutable digraph with 26 vertices, 74 edges>
gap> BookGraph(7);
<immutable bipartite symmetric digraph with bicomponent sizes 8 and 8>
gap> IsSymmetricDigraph(BookGraph(24));
true
gap> IsBipartiteDigraph(BookGraph(24));
true

3.5-8 StackedBookGraph

The stacked book graph is the Cartesian product of the symmetric closure of the chain digraph with n vertices (as the "book spine") and the \(\textit{m}+1\) star graph (as the "pages"). For more details on the stacked book graph please refer to https://mathworld.wolfram.com/StackedBookGraph.html.

See DigraphCartesianProduct (3.3-32), DigraphSymmetricClosure (3.3-12), ChainDigraph (3.5-9), and StarGraph (3.5-43).

gap> StackedBookGraph(1, 1);
<immutable bipartite symmetric digraph with bicomponent sizes 1 and 1>
gap> StackedBookGraph(1, 2);
<immutable bipartite symmetric digraph with bicomponent sizes 2 and 2>
gap> StackedBookGraph(3, 4);
<immutable bipartite symmetric digraph with bicomponent sizes 8 and 8>
gap> StackedBookGraph(IsMutable, 12, 5);
<mutable digraph with 65 vertices, 224 edges>
gap> StackedBookGraph(5, 5);
<immutable bipartite symmetric digraph with bicomponent sizes 13 and 1\
7>
gap> IsSymmetricDigraph(StackedBookGraph(24, 8));
true
gap> IsBipartiteDigraph(StackedBookGraph(24, 8));
true

3.5-9 ChainDigraph

If n is a positive integer, this function returns a chain with n vertices and n - 1 edges. Specifically, for each vertex i (with i < n), there is a directed edge with source i and range i + 1.

The DigraphReflexiveTransitiveClosure (3.3-13) of a chain represents a total order.

gap> ChainDigraph(42);
<immutable chain digraph with 42 vertices>
gap> ChainDigraph(IsMutableDigraph, 10);
<mutable digraph with 10 vertices, 9 edges>

3.5-10 CirculantGraph

If n is an integer greater than 1, and par is a list of integers that are contained in [1..n] then this operation returns a circulant graph. The circulant graph is a graph on n vertices, where for each element \(j\) of par, the \(i\)th vertex is adjacent to the \((i + j)\)th and \((i - j)\)th vertices.

If par is \([1]\), then the graph is the nth cyclic graph. If par is [1,2,...,Int(n/2)], then the graph is the complete graph on n vertices. If n is at least 4 and par is [1,n] then the graph is the nth Mobius ladder graph.

A circulant graph is biconnected, cyclic, Hamiltonian, regular, and vertex transitive.

gap> D := CirculantGraph(6, [1, 2, 3]);
<immutable Hamiltonian biconnected vertex-transitive symmetric digraph\
 with 6 vertices, 30 edges>
gap> IsIsomorphicDigraph(D, CompleteDigraph(6));
true

3.5-11 CompleteDigraph

If n is a non-negative integer, this function returns the complete digraph with n vertices. See IsCompleteDigraph (6.2-5).

gap> CompleteDigraph(20);
<immutable complete digraph with 20 vertices>
gap> CompleteDigraph(IsMutableDigraph, 10);
<mutable digraph with 10 vertices, 90 edges>

3.5-12 CompleteBipartiteDigraph

A complete bipartite digraph is a digraph whose vertices can be partitioned into two non-empty vertex sets, such there exists a unique edge with source i and range j if and only if i and j lie in different vertex sets.

If m and n are positive integers, this function returns the complete bipartite digraph with vertex sets of sizes m (containing the vertices [1 .. m]) and n (containing the vertices [m + 1 .. m + n]).

gap> CompleteBipartiteDigraph(2, 3);
<immutable complete bipartite digraph with bicomponent sizes 2 and 3>
gap> CompleteBipartiteDigraph(IsMutableDigraph, 3, 2);
<mutable digraph with 5 vertices, 12 edges>

3.5-13 CompleteMultipartiteDigraph

For a list orders of n positive integers, this function returns the digraph containing n independent sets of vertices of orders [l[1] .. l[n]]. Moreover, each vertex is adjacent to every other not contained in the same independent set.

gap> CompleteMultipartiteDigraph([5, 4, 2]);
<immutable complete multipartite digraph with 11 vertices, 76 edges>
gap> CompleteMultipartiteDigraph(IsMutableDigraph, [5, 4, 2]);
<mutable digraph with 11 vertices, 76 edges>

3.5-14 CycleDigraph

If n is a positive integer, then these functions return a cycle digraph with n vertices and n edges. Specifically, for each vertex i (with i < n), there is a directed edge with source i and range i + 1. In addition, there is an edge with source n and range 1.

gap> CycleDigraph(1);
<immutable digraph with 1 vertex, 1 edge>
gap> CycleDigraph(123);
<immutable cycle digraph with 123 vertices>
gap> CycleDigraph(IsMutableDigraph, 10);
<mutable digraph with 10 vertices, 10 edges>
gap> DigraphCycle(4) = CycleDigraph(4);
true

3.5-15 CycleGraph

If n is an integer greater than 2 then this operation returns the nth cycle graph, consisting of the cycle on n vertices. The cycle graph, unlike the cycle digraph, is symmetric. The cycle graph has n vertices and n undirected edges. The cycle graph is simple so the non-simple graphs with a single vertex and single loop and with two vertices and two edges between them are excluded.

gap> D := CycleGraph(7);
<immutable symmetric digraph with 7 vertices, 14 edges>

3.5-16 EmptyDigraph

If n is a non-negative integer, this function returns the empty or null digraph with n vertices. An empty digraph is one with no edges.

gap> EmptyDigraph(20);
<immutable empty digraph with 20 vertices>
gap> NullDigraph(10);
<immutable empty digraph with 10 vertices>
gap> EmptyDigraph(IsMutableDigraph, 10);
<mutable empty digraph with 10 vertices>

3.5-17 GearGraph

If n is a positive integer at least 3, then this operation returns the gear graph with 2n + 1 vertices and 3n undirected edges. The nth gear graph is the 2th cycle graph with one additional central vertex, to which every other vertex of the cycle is connected. The gear graph is a symmetric digraph. A gear graph is a Matchstick graph, that is it is simple with a planar graph embedding, and is a unit-distance graph (that is, it can be embedded into the Euclidean plane with vertices being distinct points and edges having length 1).

gap> D := GearGraph(4);
<immutable symmetric digraph with 9 vertices, 24 edges>
gap> ChromaticNumber(D);
2
gap> IsVertexTransitive(D);
false

3.5-18 HaarGraph

If n is a positive integer then this operation returns the Haar graph \(H(\textit{n})\).

The number of vertices in the Haar graph \(H(\textit{n})\) is equal to twice \(m\), where \(m\) is the number of digits required to represent n in binary. These vertices are arranged into bicomponents [1..m] and [m+1..2*m]. Vertices \(i\) and \(j\) in different bicomponents are adjacent by a symmetric pair of edges if and only if the binary representation of n has a 1 in position (\(j-i\) modulo \(m\)) + 1 from the left.

gap> HaarGraph(3);
<immutable bipartite vertex-transitive symmetric digraph with bicompon\
ent sizes 2 and 2>
gap> D := HaarGraph(16);
<immutable bipartite vertex-transitive symmetric digraph with bicompon\
ent sizes 5 and 5>

3.5-19 HalvedCubeGraph

If n is a positive integer at least 1, then this operation returns the nth halved cube graph, the graph of the n- demihypercube. The vertices of the graph are those of the nth- hypercube, with two vertices adjacent if and only if they are at distance 1 or 2 from each other. Equivalent constructions are as the second graph power of the n-1th hypercube graph, or as with vertices labelled as the binary numbers where two vertices are adjacent if they differ in a single bit, or with vertices labelled with the subset of binary numbers with even Hamming weight, with edges connecting vertices with Hamming distance exactly 2. The Halved Cube graph is distance regular and contains a Hamiltonian cycle.

gap> D := HalvedCubeGraph(3);
<immutable Hamiltonian connected symmetric digraph with 4 vertices, 12\
 edges>
gap> IsDistanceRegularDigraph(D);
true
gap> IsHamiltonianDigraph(D);
true

3.5-20 HanoiGraph

If n is positive integer then this operation returns the nth Hanoi graph. The Hanoi graph's vertices represent the possible states of the 'Tower of Hanoi' puzzle on three 'towers', while its edges represent possible moves. The Hanoi graph has 3^n vertices, and 3 * (3^n - 1) / 2 undirected edges.

The Hanoi graph is Hamiltonian. The graph superficially resembles the Sierpinski triangle. The graph is also a 'penny graph' - a graph whose vertices can be considered to be non-overlapping unit circles on a flat surface, with two vertices adjacent only if the unit circles touch at a single point. Thus the Hanoi graph is planar.

gap> D := HanoiGraph(5);
<immutable Hamiltonian connected symmetric digraph with 243 vertices, \
726 edges>
gap> IsPlanarDigraph(D);
true

3.5-21 HelmGraph

If n is a positive integer at least 3, then this operation returns the nth helm graph. The helm graph is the n-1th wheel graph with, for each external vertex of the 'wheel', adjoining a new vertex incident only to the first vertex. That is, the graph looks similar to a ship's helm.

gap> D := HelmGraph(4);
<immutable symmetric digraph with 9 vertices, 24 edges>

3.5-22 HypercubeGraph

If n is a non-negative integer, then this operation returns the nth hypercube graph. The graph has 2^n vertices and 2^(n-1)n edges. It is formed from the vertices and edges of the n-dimensional hypercube. Alternatively, the graph can be constructed by labelling each vertex with the binary numbers, with two vertices adjacent if they have Hamming distance exactly one. The hypercube graphs are Hamiltonian, distance-transitive and therefore distance-regular, and bipartite.

gap> D := HypercubeGraph(5);
<immutable Hamiltonian connected bipartite symmetric digraph with bico\
mponent sizes 16 and 16>

3.5-23 JohnsonDigraph

If n and k are non-negative integers, then this operation returns a symmetric digraph which corresponds to the undirected Johnson graph \(J(n, k)\).

The Johnson graph \(J(n, k)\) has vertices given by all the k-subsets of the range [1 .. n], and two vertices are connected by an edge if and only if their intersection has size \(\textit{k} - 1\).

gap> gr := JohnsonDigraph(3, 1);
<immutable symmetric digraph with 3 vertices, 6 edges>
gap> OutNeighbours(gr);
[ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ]
gap> gr := JohnsonDigraph(4, 2);
<immutable symmetric digraph with 6 vertices, 24 edges>
gap> OutNeighbours(gr);
[ [ 2, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ], 
  [ 1, 3, 4, 6 ], [ 2, 3, 4, 5 ] ]
gap> JohnsonDigraph(1, 0);
<immutable empty digraph with 1 vertex>
gap> JohnsonDigraph(IsMutableDigraph, 1, 0);
<mutable empty digraph with 1 vertex>

3.5-24 KellerGraph

If n is a nonnegative integer then this operation returns the nth or n-dimensional Keller graph. The graph has vertices given by the n-tuples on the set \([0, 1, 2, 3]\). Two vertices are adjacent if their respective tuples are such that they differ in at least two coordinates and in at least one coordinate the difference between the two is 2 mod 4. The Keller graph has 4^n vertices.

The Keller graphs were constructed with the intention of finding counterexamples to Keller's conjecture (https://mathworld.wolfram.com/KellersConjecture.html), and has been used since for testing maximum clique algorithms.

If n is 1 then the graph is empty, for n greater than 1 the chromatic number of the Keller graph is 2^n and the graph is Hamiltonian.

gap> D := KellerGraph(3);
<immutable Hamiltonian connected symmetric digraph with 64 vertices, 2\
176 edges>
gap> ChromaticNumber(D);
8

3.5-25 KingsGraph

If m and n are positive integers, then this operation returns the king's graph of an m by n chessboard, as a symmetric digraph.

The king's graph represents all possible moves of the king chess piece across a chessboard. An m by n chessboard is a grid of m columns ("files") and n rows ("ranks") that intersect in squares. Orthogonally adjacent squares are alternately colored light and dark, with the square in the first rank and file being dark.

The king can move only to any orthogonally or diagonally adjacent square. Thus the m * n vertices of the king's graph can be placed onto the m * n squares of an m by n chessboard, such that two vertices are adjacent in the digraph if and only if the corresponding squares are orthogonally or diagonally adjacent on the chessboard.

gap> KingsGraph(8, 8);
<immutable connected symmetric digraph with 64 vertices, 420 edges>
gap> D := KingsGraph(IsMutable, 2, 7);
<mutable digraph with 14 vertices, 62 edges>
gap> IsPlanarDigraph(D);
true
gap> D := KingsGraph(3, 3);
<immutable connected symmetric digraph with 9 vertices, 40 edges>
gap> OutNeighbors(D);
[ [ 2, 4, 5 ], [ 1, 3, 5, 4, 6 ], [ 2, 6, 5 ], [ 5, 1, 7, 2, 8 ], 
  [ 4, 6, 2, 8, 3, 7, 1, 9 ], [ 5, 3, 9, 8, 2 ], [ 8, 4, 5 ], 
  [ 7, 9, 5, 6, 4 ], [ 8, 6, 5 ] ]
gap> IsSubdigraph(QueensGraph(3, 4), KingsGraph(3, 4));
true

3.5-26 KneserGraph

If n and k are integers greater than 0, with k less than n, then this operation returns the (n,k)-th Kneser graph. The Kneser graph's vertices correspond to the k- element subsets of a set of n elements, with two vertices being adjacent if and only if the subsets are disjoint. The graph has Binomial(n, k) vertices and Binomial(n, k) * Binomial(n - k, k) edges. Kneser graphs are regular, edge transitive, and vertex transitive. If k is 1, then the graph is the complete graph on n vertices. If (n, k) is (2m-1, n-1), then the graph is the mth Odd graph. The Petersen graph is the \((5, 2)\)th Kneser graph.

If n >= 2k then the graph's chromatic number is n - 2k + 2, and otherwise is 1. The Kneser graph contains a Hamiltonian cycle if n >= ((3 + 5 ^ 0.5) / 2)k + 1. The graph has clique number equal to the floor of n / k.

gap> D := KneserGraph(7, 3);
<immutable edge- and vertex-transitive symmetric digraph with 35 verti\
ces, 140 edges>
gap> IsRegularDigraph(D);
true
gap> ChromaticNumber(D);
3
gap> CliqueNumber(D);
2

3.5-27 KnightsGraph

If m and n are positive integers, then this operation returns the knight's graph of an m by n chessboard, as a symmetric digraph.

A knight's graph represents all possible moves of the knight chess piece across a chessboard. An m by n chessboard is a grid of m columns ("files") and n rows ("ranks") that intersect in squares. Orthogonally adjacent squares are alternately colored light and dark, with the square in the first rank and file being dark.

The m * n vertices of the knight's graph can be placed onto the m * n squares of an m by n chessboard, such that two vertices are adjacent in the digraph if and only if a knight can move between the corresponding squares in a single turn.

gap> D := KnightsGraph(8, 8);
<immutable connected symmetric digraph with 64 vertices, 336 edges>
gap> IsConnectedDigraph(D);
true
gap> D := KnightsGraph(3, 3);
<immutable symmetric digraph with 9 vertices, 16 edges>
gap> IsConnectedDigraph(D);
false
gap> KnightsGraph(IsMutable, 3, 9);
<mutable digraph with 27 vertices, 88 edges>

3.5-28 LindgrenSousselierGraph

If n is an integer greater than 0, then this operation returns the nth Lindgren-Sousselier graph, an infinite family of hyophamiltonian graphs - a graph that is non-Hamiltonian but removing any vector gives a Hamiltonian graph. The graph has 6n+4 vertices and 15 + 10(n-1) undirected edges. The first Lindgren-Sousselier graph is the Petersen graph, and is in fact the smallest hyophamiltonian graph.

gap> D := LindgrenSousselierGraph(3);
<immutable symmetric digraph with 22 vertices, 70 edges>
gap> IsHamiltonianDigraph(D);
false
gap> IsHamiltonianDigraph(DigraphRemoveVertex(D, 1));
true
gap> IsIsomorphicDigraph(LindgrenSousselierGraph(1), PetersenGraph());
true

3.5-29 LollipopGraph

If m and n are positive integers, then this operation returns the (m,n)-lollipop graph. As defined at https://en.wikipedia.org/wiki/Lollipop_graph, this consists of a complete digraph on the vertices [1..m] (the 'head' of the lollipop), and the symmetric closure of a chain digraph on the remaining n vertices (the 'stick'), connected by a bridge (the edge [m, m+1] and its reverse).

gap> D := LollipopGraph(5, 3);
<immutable connected symmetric digraph with 8 vertices, 26 edges>
gap> CliqueNumber(D);
5
gap> DigraphUndirectedGirth(D);
3
gap> LollipopGraph(IsMutableDigraph, 3, 8);
<mutable digraph with 11 vertices, 22 edges>

3.5-30 MobiusLadderGraph

If n is a positive integer at least 4, then this operation returns the Mobius ladder graph that is obtained by introducing a 'twist' in the nth prism graph, similar to the construction of a Mobius strip. The Mobius ladder graph is isomorphic to the circulant graph Ci(2n, [1, n]). The Mobius ladders are cubic, symmetric, Hamiltonian, vertex-transitive, and graceful. They are also non-planar and apex, meaning removing a single vertex produces a planar graph.

gap> D := MobiusLadderGraph(7);
<immutable symmetric digraph with 14 vertices, 42 edges>
gap> IsHamiltonianDigraph(D);
true
gap> IsVertexTransitive(D);
true
gap> IsPlanarDigraph(D);
false
gap> D2 := DigraphRemoveVertex(D, 1);
<immutable digraph with 13 vertices, 36 edges>
gap> IsPlanarDigraph(D2);
true

3.5-31 MycielskiGraph

If n is an integer greater than 1, then this operation returns the nth Mycielski graph. The Mycielskian of a triangle-free graph is a construction that adds vertices and edges to produce a new graph that is still triangle-free but has a larger chromatic number. The Mycielski graphs are a series of graphs with this construction repeated, starting with the complete graph on two vertices. The graph has 3 * 2^(n-2) - 1 vertices, with the number of edges being (18 - 27 * 2 ^ n + 14 * 3 ^ n) / 36.

The Mycielski graph has chromatic number equal to n, clique number equal to \(2\), and is Hamiltonian. The graph is in fact the graph with chromatic number n with the least possible vertices.

gap> D := MycielskiGraph(4);
<immutable Hamiltonian connected symmetric digraph with 11 vertices, 4\
0 edges>
gap> ChromaticNumber(D);
4
gap> CliqueNumber(D);
2

3.5-32 OddGraph

If n is an integer greater than 0, then this operation returns the nth odd graph. The odd graph has vertices labelled with the n-1-subsets of a 2n-1-set, with two vertices adjacent if and only if their subsets are disjoint. The nth odd graph is the (2n-1, n-1)-th Kneser graph. The graph has Binomial(2n-1, n-1) vertices and n * Binomial(2n-1, n-1) / 2 edges.

The odd graph is regular and distance transitive (and therefore distance regular). They have chromatic number equal to 3, and all Odd graphs with n greater than 3 are Hamiltonian. They are also vertex and edge transitive.

gap> D := OddGraph(4);
<immutable edge- and vertex-transitive symmetric digraph with 35 verti\
ces, 140 edges>
gap> IsIsomorphicDigraph(D, KneserGraph(7, 3));
true
gap> ChromaticNumber(D);
3

3.5-33 PathGraph

If n is a non-negative integer then this operation returns the nth path graph, consisting of the path on n vertices. This is the symmetric closure of the ChainDigraph (3.5-9). The path graph has n vertices and n-1 edges. The path graph is an undirected tree.

gap> D := PathGraph(12);
<immutable undirected tree digraph with 12 vertices>

3.5-34 PermutationStarGraph

If n is an integer at greater than 0 and k is an integer greater than 1, and k less than or equal to n, then this operation returns the (n, k)-th permutation star graph. The vertices of the graph are given by the k-length ordered subsets of an n-set, with two vertices being adjacent if one is labelled p1 p2 p3 ... pi ... pk, and the other is either labelled pi p2 p3 ... p1 ... pk, or labelled x p2 p3 ... pi ... pk where x is in [1..n] and is not equal to p1. The graph has n! / (n - k)! vertices.

The permutation star graph is regular and vertex transitive. It has diameter 2k - 1 if k less than or equal to Int(n / 2), and diameter Int((n - 1) / 2) + k if k >= Int(n / 2) + 1.

gap> D := PermutationStarGraph(6, 2);
<immutable vertex-transitive symmetric digraph with 30 vertices, 150 e\
dges>
gap> DigraphDiameter(D);
3

3.5-35 PetersenGraph

"The Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring."

gap> ChromaticNumber(PetersenGraph());
3
gap> PetersenGraph(IsMutableDigraph);
<mutable digraph with 10 vertices, 30 edges>

3.5-36 GeneralisedPetersenGraph

If n is a positive integer and k is a non-negative integer less than n / 2, then this operation returns the generalised Petersen graph \(GPG(\textit{n}, k)\).

"The generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins."

gap> GeneralisedPetersenGraph(7, 2);
<immutable symmetric digraph with 14 vertices, 42 edges>
gap> GeneralisedPetersenGraph(40, 1);
<immutable symmetric digraph with 80 vertices, 240 edges>
gap> D := GeneralisedPetersenGraph(5, 2);
<immutable symmetric digraph with 10 vertices, 30 edges>
gap> IsIsomorphicDigraph(D, PetersenGraph());
true
gap> GeneralisedPetersenGraph(IsMutableDigraph, 9, 4);
<mutable digraph with 18 vertices, 54 edges>

3.5-37 PrismGraph

If n is a positive integer at least 3, then this operation returns the prism graph that is the skeleton of the n-prism. It has 2n vertices and 3n undirected edges. The prism graph is a symmetric digraph. The nth prism graph is isomorphic to the graph Cartesian product of the second path graph and the nth cycle graph, isomorphic to the generalised Petersen graph GP(n,1). If n is odd then the prism graph is isomorphic to the Circulant graph Ci(2n, [2,n]). The prism graph is Hamiltonian.

gap> D := PrismGraph(4);
<immutable symmetric digraph with 8 vertices, 24 edges>
gap> IsHamiltonianDigraph(D);
true
gap> D := PrismGraph(5);
<immutable symmetric digraph with 10 vertices, 30 edges>
gap> IsIsomorphicDigraph(D, CirculantGraph(10, [2, 5]));
true

3.5-38 StackedPrismGraph

If n is an integer at least 3 and k is a positive integer then this operation returns the (n,k)-th stacked prism graph. The graph is k concentric n-Cycle graphs connected by spokes. The stacked prism is the graph Cartesian product of the nth cycle graph and the kth path graph. The graph has nk vertices and n(2k - 1) undirected edges. If k is 1 then the graph is the nth cycle graph, if k is 2 then the graph is the prism graph.

gap> D := StackedPrismGraph(5, 2);
<immutable symmetric digraph with 10 vertices, 30 edges>
gap> IsIsomorphicDigraph(D, PrismGraph(5));
true

3.5-39 QueensGraph

If m and n are positive integers, then this operation returns the queen's graph of an m by n chessboard, as a symmetric digraph.

The queen's graph represents all possible moves of the queen chess piece across a chessboard. An m by n chessboard is a grid of m columns ("files") and n rows ("ranks") that intersect in squares. Orthogonally adjacent squares are alternately colored light and dark, with the square in the first rank and file being dark.

The m * n vertices of the queen's graph can be placed onto the m * n squares of an m by n chessboard, such that two vertices are adjacent in the digraph if and only if the queen can move between the corresponding squares in a single turn. A legal queen's move is defined as one which moves the queen to an (orthogonally or diagonally) adjacent square, or to a square which can be reached through a series of such moves, with all of the small moves being in the same direction.

Note that the QueensGraph is the DigraphEdgeUnion (3.3-30) of the RooksGraph (3.5-40) and the BishopsGraph (3.5-5) of the same dimensions.

The chosen correspondence between vertices and chess squares is given by DigraphVertexLabels (5.1-12). In more detail, the vertices of the digraph are labelled by elements of the Cartesian product [1..m] x [1..n], where the first entry indexes the column (file) of the square in the chessboard, and the second entry indexes the row (rank) of the square. (Note that the files are traditionally indexed by the lowercase letters of the alphabet). The vertices are sorted in ascending order, first by row (second component) and then column (first component). If the optional first argument filt is present, then this should specify the category or representation the digraph being created will belong to. For example, if filt is IsMutableDigraph (3.1-2), then the digraph being created will be mutable, if filt is IsImmutableDigraph (3.1-3), then the digraph will be immutable. If the optional first argument filt is not present, then IsImmutableDigraph (3.1-3) is used by default.

gap> QueensGraph(2, 5);
<immutable connected symmetric digraph with 10 vertices, 66 edges>
gap> D := QueensGraph(4, 3);
<immutable connected symmetric digraph with 12 vertices, 92 edges>
gap> IsRegularDigraph(D);
false
gap> QueensGraph(6, 9) =
>    DigraphEdgeUnion(RooksGraph(6, 9), BishopsGraph(6, 9));
true

3.5-40 RooksGraph

If m and n are positive integers, then this operation returns the rook's graph of an m by n chessboard, as a symmetric digraph.

A rook's graph represents all possible moves of the rook chess piece across a chessboard. An m by n chessboard is a grid of m columns ("files") and n rows ("ranks") that intersect in squares. Orthogonally adjacent squares are alternately colored light and dark, with the square in the first rank and file being dark.

The m * n vertices of the rook's graph can be placed onto the m * n squares of an m by n chessboard, such that two vertices are adjacent in the digraph if and only if a rook can move between the corresponding squares in a single turn. A legal rook's move is defined as one which moves the rook to an orthogonally adjacent square, or to a square which can be reached through a series of such moves, with all of the small moves being in the same direction.

gap> D := RooksGraph(7, 4);
<immutable connected regular symmetric digraph with 28 vertices, 252 e\
dges>
gap> RooksGraph(1, 8);
<immutable connected regular symmetric digraph with 8 vertices, 56 edg\
es>

3.5-41 SquareGridGraph

If n and k are positive integers, then this operation returns a square grid graph of dimension n by k.

A square grid graph of dimension n by k is the DigraphCartesianProduct (3.3-32) of the symmetric closures of the chain digraphs with n and k vertices; see DigraphSymmetricClosure (3.3-12) and ChainDigraph (3.5-9).

In particular, the n * k vertices can be arranged into an n by k grid such that two vertices are adjacent in the digraph if and only if they are orthogonally adjacent in the grid. The correspondence between vertices and grid positions is given by DigraphVertexLabels (5.1-12).

gap> SquareGridGraph(5, 5);
<immutable connected bipartite symmetric digraph with bicomponent size\
s 13 and 12>
gap> GridGraph(IsMutable, 3, 4);
<mutable digraph with 12 vertices, 34 edges>

3.5-42 TriangularGridGraph

If n and k are positive integers, then this operation returns a triangular grid graph of dimension n by k.

A triangular grid graph of dimension n by k is a symmetric digraph constructed from the SquareGridGraph (3.5-41) of the same dimensions, where additionally two vertices are adjacent in the digraph if they are diagonally adjacent in the grid, on a particular one of the diagonals. The correspondence between vertices and grid positions is given by DigraphVertexLabels (5.1-12). More specifically, the particular diagonal is the one such that, the vertices corresponding to the grid positions [2,1] and [1,2] are adjacent (if they exist), but those corresponding to [1,1] and [2,2] are not.

gap> TriangularGridGraph(3, 3);
<immutable connected symmetric digraph with 9 vertices, 32 edges>
gap> TriangularGridGraph(IsMutable, 3, 3);
<mutable digraph with 9 vertices, 32 edges>

3.5-43 StarGraph

If k is a positive integer, then this operation returns the star graph with k vertices, which is the undirected tree in which vertex 1 is adjacent to all other vertices. If k is at least 2, then this is the complete bipartite digraph with bicomponents [1] and [2 .. k].

See IsUndirectedTree (6.6-9), IsCompleteBipartiteDigraph (6.2-4), and DigraphBicomponents (5.4-13).

gap> StarGraph(IsMutable, 10);
<mutable digraph with 10 vertices, 18 edges>
gap> StarGraph(5);
<immutable complete bipartite digraph with bicomponent sizes 1 and 4>
gap> IsSymmetricDigraph(StarGraph(3));
true
gap> IsUndirectedTree(StarGraph(3));
true

3.5-44 TadpoleGraph

The tadpole graph is the symmetric closure of the disjoint union of the cycle digraph on [1..m] (the 'head' of the tadpole) and the chain digraph on [m+1..m+n] (the 'tail' of the tadpole), along with the additional edges [1, m+1] and [1, m+1] which connect the 'head' and the 'tail'. For more details on the tadpole graph please refer to https://en.wikipedia.org/wiki/Tadpole_graph.

See DigraphSymmetricClosure (3.3-12), DigraphDisjointUnion (3.3-29), CycleDigraph (3.5-14), and ChainDigraph (3.5-9).

gap> TadpoleGraph(10, 15);
<immutable symmetric digraph with 25 vertices, 50 edges>
gap> TadpoleGraph(IsMutableDigraph, 5, 6);
<mutable digraph with 11 vertices, 22 edges>
gap> IsSymmetricDigraph(TadpoleGraph(3, 5));
true

3.5-45 WalshHadamardGraph

If n is a positive integer at least 1, then this operation returns the Hadamard graph constructed from the nth Hadamard matrix (of dimension 2^n) as constructed by Joseph Walsh. A Hadamard matrix is a square matrix with entries either \(1\) or \(-1\), such that all the rows are mutually orthogonal. The nth Walsh Hadamard graph is a graph on 4n matrices split into four categories \(r_i+, r_i-, c_i+, c_i-\). If \(h_ij\) are the elements of the nth Walsh matrix, then if \(h_ij = 1\) then \((r_i+, c_j+)\) and \((r_i-, c_j-)\) are edges, if \(h_ij = -1\) then \((r_i+, c_j-)\) and \((r_i-, c_j+)\) are edges. Walsh Hadamard graphs are distance transitive and distance regular.

gap> D := WalshHadamardGraph(5);
<immutable symmetric digraph with 64 vertices, 1024 edges>
gap> IsDistanceRegularDigraph(D);
true

3.5-46 WebGraph

If n is an integer at least 3 then this operation returns the nth web graph. The web graph is the (n,3)-th stacked prism graph with the edges of the outer cycle removed. The graph has 3n vertices and 4n undirected edges.

gap> D := WebGraph(5);
<immutable symmetric digraph with 15 vertices, 40 edges>

3.5-47 WheelGraph

If n is a positive integer at least 4, then this operation returns the nth wheel graph. The Wheel graph is formed from an n-1 cycle graph with a single additional vertex adjacent to all vertices of the cycle. The graph has n vertices and 2(n-1) edges. Wheel graphs are the skeletons of n-1 pyramids, and are self-dual. If n is odd, then the chromatic number of the wheel graph is 3 and the Wheel graph is perfect, and it is 4 otherwise. The wheel graph is also Hamiltonian and planar.

gap> D := WheelGraph(8);
<immutable Hamiltonian connected symmetric digraph with 8 vertices, 28\
 edges>
gap> ChromaticNumber(D);
4
gap> IsHamiltonianDigraph(D);
true

3.5-48 WindmillGraph

If n and m are integers greater than 1 then this operation returns the (n, m)-th windmill graph. The windmill graph is formed from m copies of the complete graph on n vertices with one shared vertex. The graph has m(n - 1) + 1 vertices and m * n * (n - 1) / 2 undirected edges. The windmill graph has chromatic number n and diameter 2.

3 Creating digraphs

3.1 Creating digraphs

3.1-1 IsDigraph

3.1-2 IsMutableDigraph

3.1-3 IsImmutableDigraph

3.1-4 IsCayleyDigraph

3.1-5 IsDigraphWithAdjacencyFunction

3.1-6 DigraphByOutNeighboursType

3.1-7 Digraph

3.1-8 DigraphByAdjacencyMatrix

3.1-9 DigraphByEdges

3.1-10 EdgeOrbitsDigraph

3.1-11 DigraphByInNeighbours

3.1-12 CayleyDigraph

3.1-13 ListNamedDigraphs

3.2 Changing representations

3.2-1 AsBinaryRelation

3.2-2 AsDigraph

3.2-3 Graph

3.2-4 AsGraph

3.2-5 AsTransformation

3.3 New digraphs from old

3.3-1 DigraphImmutableCopy

3.3-2 DigraphImmutableCopyIfImmutable

3.3-3 InducedSubdigraph

3.3-4 ReducedDigraph

3.3-5 MaximalSymmetricSubdigraph

3.3-6 MaximalAntiSymmetricSubdigraph

3.3-7 UndirectedSpanningForest

3.3-8 DigraphShortestPathSpanningTree

3.3-9 QuotientDigraph

3.3-10 DigraphReverse

3.3-11 DigraphDual

3.3-12 DigraphSymmetricClosure

3.3-13 DigraphTransitiveClosure

3.3-14 DigraphTransitiveReduction

3.3-15 DigraphAddVertex

3.3-16 DigraphAddVertices

3.3-17 DigraphAddEdge

3.3-18 DigraphAddEdgeOrbit

3.3-19 DigraphAddEdges

3.3-20 DigraphRemoveVertex

3.3-21 DigraphRemoveVertices

3.3-22 DigraphRemoveEdge

3.3-23 DigraphRemoveEdgeOrbit

3.3-24 DigraphRemoveEdges

3.3-25 DigraphRemoveLoops

3.3-26 DigraphRemoveAllMultipleEdges

3.3-27 DigraphContractEdge

3.3-28 DigraphReverseEdges

3.3-29 DigraphDisjointUnion

3.3-30 DigraphEdgeUnion

3.3-31 DigraphJoin

3.3-32 DigraphCartesianProduct

3.3-33 DigraphDirectProduct

3.3-34 ConormalProduct

3.3-35 HomomorphicProduct

3.3-36 LexicographicProduct

3.3-37 ModularProduct

3.3-38 StrongProduct

3.3-39 DigraphCartesianProductProjections

3.3-40 DigraphDirectProductProjections

3.3-41 LineDigraph

3.3-42 LineUndirectedDigraph

3.3-43 DoubleDigraph

3.3-44 BipartiteDoubleDigraph

3.3-45 DigraphAddAllLoops

3.3-46 DistanceDigraph

3.3-47 DigraphClosure

3.3-48 DigraphMycielskian

3.4 Random digraphs

3.4-1 RandomDigraph

3.4-2 RandomMultiDigraph

3.4-3 RandomTournament

3.4-4 RandomLattice

3.5 Standard examples

3.5-1 AndrasfaiGraph

3.5-2 BananaTree

3.5-3 BinaryTree

3.5-4 BinomialTreeGraph