In this Chapter we give functions for accessing the G-half-arc-transitive 4-valent graphs stored in this package, and related properties. Currently, this package contains all G-half-arc-transitive 4-valent graphs on up to 1000 vertices. For information and references on these graphs, see [PSV13a].
Let Γ be a simple graph (undirected, loopless, without multiple edges). Then Γ is 4-valent (or tetravalent) if each vertex of the graph has exactly 4 neighbours.
The graph Γ is G-half-arc-transitive if G is a group of automorphisms of Γ which acts transitively on the vertices and edges of Γ, but not on the arcs of Γ.
In this Section we introduce functions for the access to the G-half-arc-transitive 4-valent graphs stored in the GraphSym package.
‣ GHAT4ValentGraph( n, i[, data] ) | ( function ) |
Returns: A digraph.
Given positive integers n,i, this function returns the ith G-half-arc-transitive 4-valent graph 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 SetGHAT4ValentGraphProps (5.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graph.
gap> GHAT4ValentGraph(600,20);
<immutable symmetric digraph with 600 vertices, 2400 edges>
gap> GHAT4ValentGraph(600,81);
fail
‣ AllGHAT4ValentGraphs( n[, data] ) | ( function ) |
Returns: A list.
Given a positive integer n, this function returns a list containing all G-half-arc-transitive 4-valent graphs 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 SetGHAT4ValentGraphProps (5.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graphs.
gap> gammas:=AllGHAT4ValentGraphs(600);;
gap> Length(gammas);
80
‣ GHAT4ValentGraphIterator( n[, data] ) | ( function ) |
Returns: An iterator.
Given a positive integer n, this function returns an iterator over all G-half-arc-transitive 4-valent graphs 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 SetGHAT4ValentGraphProps (5.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graphs.
gap> cnt:=0;; iter:=GHAT4ValentGraphIterator(600);;
gap> for gamma in iter do
> if HasSolvableAutGroup(gamma) then
> cnt:=cnt+1;
> fi;
> od;
gap> cnt;
57
In this Section we give the functions which give information about the G-half-arc-transitive 4-valent graph library, and the properties and attributes of the graphs it contains.
For a given G-half-arc-transitive 4-valent graph Γ stored in this package, there are several precomputed attributes stored in the GraphSym package. These include the following:
Diameter of Γ (DigraphDiameter (Digraphs: DigraphDiameter)).
Girth of Γ (DigraphUndirectedGirth (Digraphs: DigraphUndirectedGirth)).
Bipartiteness of Γ (IsBipartiteDigraph (Digraphs: IsBipartiteDigraph)).
Arc-transitivity of Γ (IsArcTransitiveDigraph (2.2-8)).
The Cayley type of Γ (CayleyType (5.2-5)).
The consistent cycle types of Γ (ConsistentCycleTypes (5.2-6)).
Now we introduce functions which are used to find information about the library and each of the graphs it stores.
‣ NrGHAT4ValentGraphs( n ) | ( function ) |
‣ NumberGHAT4ValentGraphs( n ) | ( function ) |
Returns: An integer.
Given a positive integer n, this function returns the number of G-half-arc-transitive 4-valent graphs with n vertices stored in this package.
For any positive integers n up to 1000, the current package stores all G-half-arc-transitive 4-valent graphs with n vertices.
gap> NrGHAT4ValentGraphs(600);
80
‣ GHAT4ValentGraphId( 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 AllGHAT4ValentGraphs(n) and the ith graph found when iterating through GHAT4ValentGraphIterator(n).
gap> gamma:=GHAT4ValentGraph(768,20);;
gap> GHAT4ValentGraphId(gamma);
20
‣ SetGHAT4ValentGraphProps( 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 5.2-1.
GHAT4ValentGraphId (5.2-3).
IsCayleyGraph (2.2-7).
IsVertexTransitive (Digraphs: IsVertexTransitive).
gap> gamma:=GHAT4ValentGraph(768,20);;
gap> SetGHAT4ValentGraphProps(gamma);
gap> SizeStabAut(gamma);
4
‣ CayleyType( gamma ) | ( attribute ) |
Returns: A string.
Given a G-half-arc-transitive 4-valent graph gamma from the GraphSym package such that its properties and attributes have been assigned, this function returns the Cayley type of gamma.
Let Γ be a graph. Then CayleyType(Γ) takes value as one of the following strings:
"Circ"if Γ is isomorphic to a circulant graph (a Cayley graph defined on a cyclic group).
"AbCay"if Γ is isomorphic to a Cayley graph defined on an abelian group, but not isomorphic to a circulant graph.
"Cay"if Γ is isomorphic to a Cayley graph defined on a nonabelian group, but not isomorphic to a Cayley graph defined on an abelian group.
"n-Cay"if Γ is not isomorphic to a Cayley graph.
gap> gamma:=GHAT4ValentGraph(768,20,true);;
gap> CayleyType(gamma);
"Cay"
‣ ConsistentCycleTypes( gamma ) | ( attribute ) |
Returns: A list.
Given a G-half-arc-transitive 4-valent graph gamma from the GraphSym package such that its properties and attributes have been assigned, this function returns the list of consistent cycle types of the graph gamma, with exactly one entry for each orbit of consistent cycles under the action of the automorphism group of gamma. For a G-consistent cycle C in gamma, the consistent cycle type of C is denoted as a string, starting with length of C, and with last character s if C is G-symmetric, or c if C is G-chiral.
The properties and attributes of a G-half-arc-transitive 4-valent graph that can be found in the GraphSym package can be assigned using the function SetGHAT4ValentGraphProps (5.2-4), or loaded automatically by the functions GHAT4ValentGraph (5.1-1), AllGHAT4ValentGraphs (5.1-2) or GHAT4ValentGraphIterator (5.1-3).
Let Γ be a graph with group of automorphisms G, and cycle C. The cycle C is G-consistent if there is an element of G which induces a 1-step rotation on C. A G-consistent cycle C is G-symmetric if there is an element of G which reverses the orientation of C. A G-consistent cycle C is G-chiral if there is no element of G which reverses the orientation of C.
For information and references on consistent cycles, see [PSV13a].
gap> gamma:=GHAT4ValentGraph(768,20,true);;
gap> ConsistentCycleTypes(gamma);
[ "4s", "6s", "12s" ]
generated by GAPDoc2HTML