In this Chapter we give functions for accessing the arc-transitive 2-valent asymmetric digraphs stored in this package, and related properties. Currently, this package contains all arc-transitive 2-valent connected asymmetric digraphs on up to 1000 vertices. For information and references about these digraphs, see [PSV13a].
Let \(\Gamma\) be a digraph. Then \(\Gamma\) is asymmetric if it has no arcs for which the reverse arc is also in \(\Gamma\), and is connected if the underlying graph of \(\Gamma\) is connected. The digraph \(\Gamma\) is arc-transitive if the automorphism group of \(\Gamma\) acts transitively on the arcs of \(\Gamma\). Further, the digraph \(\Gamma\) is \(2\)-valent if each vertex of \(\Gamma\) has 2 in-neighbours and 2 out-neighbours.
In this Section we introduce functions for the access to the cubic vertex-transitive graphs stored in the GraphSym package.
‣ AT2ValentDigraph( n, i[, data] ) | ( function ) |
Returns: A digraph.
Given positive integers n,i, this function returns the ith arc-transitive 2-valent digraph with n vertices available in this package. If there is no such graph, the function returns fail.
When the optional argument data is specified, it must have value true or false. If data=true, the graph returned by this function will have been assigned the precomputed properties and attributes from SetAT2ValentDigraphProps (4.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graph.
gap> AT2ValentDigraph(300,40);
<immutable digraph with 300 vertices, 600 edges>
gap> AT2ValentDigraph(300,100);
fail
‣ AllAT2ValentDigraphs( n[, data] ) | ( function ) |
Returns: A list.
Given a positive integer n, this function returns a list containing all arc-transitive digraphs with n vertices available in this package. If there are no such graphs, the function returns fail.
When the optional argument data is specified, it must have value true or false. If data=true, the graphs returned by this function will have been assigned the precomputed properties and attributes from SetAT2ValentDigraphProps (4.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graphs.
gap> gammas:=AllAT2ValentDigraphs(300,true);;
gap> ForAny(gammas,HasAbelianVertexStabilizer);
true
‣ AT2ValentDigraphIterator( n[, data] ) | ( function ) |
Returns: A list.
Given a positive integer n, this function returns an iterator over all arc-transitive 2-valent digraphs with n vertices available in this package. If there are such no graphs, the function returns an empty iterator.
When the optional argument data is specified, it must have value true or false. If data=true, the graphs returned by this function will have been assigned the precomputed properties and attributes from SetAT2ValentDigraphProps (4.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graphs.
gap> cnt:=0;; iter:=AT2ValentDigraphIterator(100,true);;
gap> for gamma in iter do
> if HasSolvableAutGroup(gamma) then
> cnt:=cnt+1;
> fi;
> od;
gap> cnt;
15
In this Section we give the functions which give information about the arc-transitive 2-valent digraph library, and the properties and attributes of the graphs it contains.
For a given arc-transitive 2-valent digraph \(\Gamma\) stored in this package, there are several precomputed attributes stored in the GraphSym package. These include the following:
The self-reverseness of \(\Gamma\) (IsSelfReverseDigraph (4.2-5)).
The index of the reverse graph of \(\Gamma\) (AT2ValentReverseDigraphId (4.2-8)).
The arc-transitiveness of the underlying graph of \(\Gamma\) (HasATUnderlyingGraph (4.2-6)).
The underlying graph of \(\Gamma\). This is a string giving the position of the underlying graph in one of the collections of graphs found in this package (NameOfUnderlyingGraph (4.2-9)).
The maximum \(s\) such that \(\Gamma\) is \(s\)-arc-transitive (MaximumArcTransitivity (4.2-10)).
The generalised wreath digraph-ness of \(\Gamma\) (IsGeneralizedWreathDigraph (4.2-7)).
Now we introduce functions which are used to find information about the library and each of the graphs it stores.
‣ NrAT2ValentDigraphs( n ) | ( function ) |
‣ NumberAT2ValentDigraphs( n ) | ( function ) |
Returns: An integer.
Given a positive integer n, this function returns the number of arc-transitive 2-valent digraphs with n vertices stored in this package.
For any positive integers \(n\) up to 1000, arc-transitive 2-valent connected asymmetric digraphs with \(n\) vertices.
gap> NrAT2ValentDigraphs(500);
63
‣ AT2ValentDigraphId( gamma ) | ( attribute ) |
Returns: An integer.
Given a digraph gamma, if gamma is isomorphic to a graph stored in this package, this function returns the index of the graph isomorphic to gamma. Otherwise, this function returns fail.
The index i of a graph gamma in this library is the position at which the graph is stored relative to its number of vertices. In particular, if gamma has n vertices, then gamma will be the ith entry of AllAT2ValentDigraphs(n) and the ith graph found when iterating through AT2ValentDigraphIterator(n).
gap> gamma:=AT2ValentDigraph(100,5);;
gap> AT2ValentDigraphId(gamma);
5
‣ SetAT2ValentDigraphProps( gamma ) | ( function ) |
Given a digraph gamma, if this graph is isomorphic to a graph stored in this library, this function sets the properties and attributes of gamma precomputed in this package. This includes
All properties and attributes found in Subsection 4.2-1.
AT2ValentDigraphId (4.2-3).
IsArcTransitiveDigraph (2.2-8).
IsVertexTransitive (Digraphs: IsVertexTransitive).
DigraphReverse (Digraphs: DigraphReverse), which stores the reverse graph of gamma with it's library id as defined in AT2ValentDigraphId (4.2-3)).
DigraphSymmetricClosure (Digraphs: DigraphSymmetricClosure), which stores the underlying graph of gamma as described in NameOfUnderlyingGraph (4.2-9).
gap> gamma:=AT2ValentDigraph(150,5);;
gap> SetAT2ValentDigraphProps(gamma);
gap> IsGeneralizedWreathDigraph(gamma);
false
‣ IsSelfReverseDigraph( gamma ) | ( property ) |
Returns: true or false.
Given a digraph gamma, this function returns true if gamma is isomorphic to the reverse (or reverse) of gamma, and otherwise it returns false (see DigraphReverse (Digraphs: DigraphReverse) ).
gap> gamma:=AT2ValentDigraph(300,1);;
gap> IsSelfReverseDigraph(gamma);
false
gap> gamma:=AT2ValentDigraph(300,20);;
gap> IsSelfReverseDigraph(gamma);
true
‣ HasATUnderlyingGraph( gamma ) | ( property ) |
Returns: true or false.
Given a digraph gamma, this function returns true if the underlying graph of gamma is arc-transitive, and otherwise it returns false (see DigraphSymmetricClosure (Digraphs: DigraphSymmetricClosure), IsEdgeTransitive (Digraphs: IsEdgeTransitive) and IsArcTransitiveDigraph (2.2-8)).
gap> gamma:=AT2ValentDigraph(300,10);;
gap> HasATUnderlyingGraph(gamma);
false
gap> gamma:=AT2ValentDigraph(300,30,true);;
gap> HasATUnderlyingGraph(gamma);
true
‣ IsGeneralizedWreathDigraph( gamma ) | ( property ) |
Returns: true or false.
Given an arc-transitive 2-valent digraph gamma from the GraphSym package such that its properties and attributes have been assigned, this function returns true if it is isomorphic to a generalized wreath digraph, and otherwise it returns false.
The properties and attributes of an arc-transitive 2-valent digraph that can be found in the GraphSym package can be assigned using the function SetAT2ValentDigraphProps (4.2-4), or loaded automatically by the functions AT2ValentDigraph (4.1-1), AllAT2ValentDigraphs (4.1-2) or AT2ValentDigraphIterator (4.1-3).
Let \(n\) be an integer such that \(n>2\). The generalized wreath digraph, \(\overrightarrow{W}_n\), has vertex-set \(ℤ_n \times ℤ_2\). Then, two distinct vertices \((i,a),(j,b)\) are adjacent if and only if \(j-i\equiv 1 \pmod n\).
For more information on the generalized wreath digraphs, see [PSV15].
gap> gamma:=AT2ValentDigraph(700,30,true);;
gap> IsGeneralizedWreathDigraph(gamma);
false
gap> gamma:=AT2ValentDigraph(700,43,true);;
gap> IsGeneralizedWreathDigraph(gamma);
true
‣ AT2ValentReverseDigraphId( gamma ) | ( attribute ) |
Returns: An integer.
Given an arc-transitive 2-valent digraph gamma from the GraphSym package such that its properties and attributes have been assigned, this function returns the position, i, at which the reverse (or reverse) of gamma is stored (see DigraphReverse (Digraphs: DigraphReverse)). In particular, if gamma has order \(n\), then AT2ValentDigraph(\(n\),i) is the reverse graph of gamma.
The properties and attributes of an arc-transitive 2-valent digraph that can be found in the GraphSym package can be assigned using the function SetAT2ValentDigraphProps (4.2-4), or loaded automatically by the functions AT2ValentDigraph (4.1-1), AllAT2ValentDigraphs (4.1-2) or AT2ValentDigraphIterator (4.1-3).
gap> gamma:=AT2ValentDigraph(700,10,true);;
gap> AT2ValentReverseDigraphId(gamma);
9
‣ NameOfUnderlyingGraph( gamma ) | ( attribute ) |
Returns: A string.
Given an arc-transitive 2-valent digraph gamma from the GraphSym package such that its properties and attributes have been assigned, this function returns the name of the underlying graph of gamma (see DigraphSymmetricClosure (Digraphs: DigraphSymmetricClosure)).
The properties and attributes of an arc-transitive 2-valent digraph that can be found in the GraphSym package can be assigned using the function SetAT2ValentDigraphProps (4.2-4), or loaded automatically by the functions AT2ValentDigraph (4.1-1), AllAT2ValentDigraphs (4.1-2) or AT2ValentDigraphIterator (4.1-3).
The string returned will start with 3 or 4 letters, and then contain 2 numbers enclosed within "[" and "]" characters and separated by the character ";". In the following we give the 3 possible strings of letters found in these names, and their meaning:
"GWD"the underlying graph is a generalized wreath graph.
"HAT"the underlying graph is half-arc-transitive, and not a generalised wreath graph (see Chapter 6).
"GHAT"the underlying graph is \(G\)-half-arc-transitive for some subgroup of its automorphism group \(G\), but not a half-arc-transitive or generalised wreath graph (see Chapter 5).
The underlying graph corresponding to this string is then the graph in the list found in [PSV15] with the same name as the string, and indexed by the remaining two integers in the string.
gap> gamma:=AT2ValentDigraph(700,40,true);;
gap> NameOfUnderlyingGraph(gamma);
"GHAT[700;12]"
‣ MaximumArcTransitivity( gamma ) | ( attribute ) |
Returns: An integer.
Given an arc-transitive 2-valent digraph gamma from the GraphSym package such that its properties and attributes have been assigned, this function returns the maximum integer \(s\) such that gamma is \(s\)-arc-transitive.
The properties and attributes of an arc-transitive 2-valent digraph that can be found in the GraphSym package can be assigned using the function SetAT2ValentDigraphProps (4.2-4), or loaded automatically by the functions AT2ValentDigraph (4.1-1), AllAT2ValentDigraphs (4.1-2) or AT2ValentDigraphIterator (4.1-3).
An \(s\)-arc of a digraph \(\Gamma\) is an \((s+1)\)-tuple \((v_0, v_1,\dots, v_s)\) of vertices of \(\Gamma\), such that \((v_{{i−1}}, v_i)\) is an arc of \(\Gamma\) for every \(i\in \{{1,\dots, s}\}\) and \(v_{{i−1}} \not= v_{{i+1}}\) for every \(i\in \{{1,\dots,s-1}\}\). A digraph \(\Gamma\) is \(s\)-arc-transitive if the automorphism group of \(\Gamma\) acts transitively on the set of \(s\)-arcs of \(\Gamma\).
For more information on \(s\)-arc-transitive graphs, see [GR01].
gap> gamma:=AT2ValentDigraph(748,18,true);;
gap> MaximumArcTransitivity(gamma);
373
generated by GAPDoc2HTML