Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

4 Arc–transitive 2–valent digraphs
 4.1 Accessing the arc–transitive 2–valent digraphs
 4.2 Properties of the arc–transitive 2–valent digraphs and library

4 Arc–transitive 2–valent digraphs

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 Γ be a digraph. Then Γ is asymmetric if it has no arcs for which the reverse arc is also in Γ, and is connected if the underlying graph of Γ is connected. The digraph Γ is arc-transitive if the automorphism group of Γ acts transitively on the arcs of Γ. Further, the digraph Γ is 2-valent if each vertex of Γ has 2 in-neighbours and 2 out-neighbours.

4.1 Accessing the arc–transitive 2–valent digraphs

In this Section we introduce functions for the access to the cubic vertex-transitive graphs stored in the GraphSym package.

4.1-1 AT2ValentDigraph
‣ 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
    
  

4.1-2 AllAT2ValentDigraphs
‣ 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
    
  

4.1-3 AT2ValentDigraphIterator
‣ 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
    
  

4.2 Properties of the arc–transitive 2–valent digraphs and library

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.

4.2-1 Precomputed attributes of the arc–transitive 2–valent digraphs

For a given arc-transitive 2-valent digraph Γ stored in this package, there are several precomputed attributes stored in the GraphSym package. These include the following:

Now we introduce functions which are used to find information about the library and each of the graphs it stores.

4.2-2 NrAT2ValentDigraphs
‣ 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
    
  

4.2-3 AT2ValentDigraphId
‣ 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
    
  

4.2-4 SetAT2ValentDigraphProps
‣ 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

    
gap> gamma:=AT2ValentDigraph(150,5);;
gap> SetAT2ValentDigraphProps(gamma);
gap> IsGeneralizedWreathDigraph(gamma);
false
    
  

4.2-5 IsSelfReverseDigraph
‣ 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
    
  

4.2-6 HasATUnderlyingGraph
‣ 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
    
  

4.2-7 IsGeneralizedWreathDigraph
‣ 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, overrightarrowW_n, has vertex-set ℤ_n × ℤ_2. Then, two distinct vertices (i,a),(j,b) are adjacent if and only if j-i≡ 1 mod 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
    
  

4.2-8 AT2ValentReverseDigraphId
‣ 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
    
  

4.2-9 NameOfUnderlyingGraph
‣ 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]"
    
  

4.2-10 MaximumArcTransitivity
‣ 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 Γ is an (s+1)-tuple (v_0, v_1,dots, v_s) of vertices of Γ, such that (v_{i−1}, v_i) is an arc of Γ for every i∈ {1,dots, s} and v_{i−1} not= v_{i+1} for every i∈ {1,dots,s-1}. A digraph Γ is s-arc-transitive if the automorphism group of Γ acts transitively on the set of s-arcs of Γ.

For more information on s-arc-transitive graphs, see [GR01].

    
gap> gamma:=AT2ValentDigraph(748,18,true);;
gap> MaximumArcTransitivity(gamma);
373
    
  
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Bib Ind

generated by GAPDoc2HTML