In this Chapter we give functions for accessing the cubic vertex-transitive graphs stored in this package, and related properties. Currently, this package contains all connected cubic vertex-transitive graphs on up to 1280 vertices. For information and references on these graphs, see [PSV13b].
Let Γ be a simple graph (undirected, loopless, without multiple edges). Then Γ is cubic (or trivalent, or 3-valent) if each vertex of the graph has exactly 3 neighbours.
The graph Γ is vertex-transitive if the automorphism group of Γ acts transitively on the vertices of Γ.
In this Section we introduce functions for the access to the cubic vertex-transitive graphs stored in the GraphSym package.
‣ CubicVTGraph( n, i[, data] ) | ( function ) |
Returns: A digraph.
Given positive integers n,i, this function returns the ith cubic vertex-transitive 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 SetCubicVTGraphProps (2.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graph.
gap> CubicVTGraph(50,4);
<immutable symmetric digraph with 50 vertices, 150 edges>
gap> CubicVTGraph(50,10);
fail
‣ AllCubicVTGraphs( n[, data] ) | ( function ) |
Returns: A list.
Given a positive integer n, this function returns a list containing all cubic vertex-transitive 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 SetCubicVTGraphProps (2.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graphs.
gap> gammas:=AllCubicVTGraphs(50,true);;
gap> List(gammas,IsSplitPraegerXuGraph);
[ false, false, false, false, false, false, false, false, false ]
gap> gammas:=AllCubicVTGraphs(100,true);;
gap> ForAny(gammas,IsSplitPraegerXuGraph);
true
‣ CubicVTGraphIterator( n[, data] ) | ( function ) |
Returns: A list
Given a positive integer n, this function returns an iterator over all cubic vertex-transitive 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 SetCubicVTGraphProps (2.2-4). If data=false or not specified, none of these properties or attributes are given to the resulting graphs.
gap> cnt:=0;; iter:=CubicVTGraphIterator(1152,true);
<iterator>
gap> for gamma in iter do
> if IsSplitPraegerXuGraph(gamma) then cnt:=cnt+1; fi;
> od;
gap> cnt;
6
In this Section we give the functions which give information about the cubic vertex-transitive graphs library, and the properties and attributes of the graphs it contains.
For a given cubic vertex-transitive graph Γ stored in this package, there are several precomputed attributes stored in the GraphSym package. These include the following:
The diameter of Γ (DigraphDiameter (Digraphs: DigraphDiameter)).
The girth of the Γ (DigraphUndirectedGirth (Digraphs: DigraphUndirectedGirth)).
The bipartiteness of Γ (IsBipartiteDigraph (Digraphs: IsBipartiteDigraph)).
The Cayleyness of Γ (IsCayleyGraph (2.2-7)).
The arc-transitiveness of Γ (IsArcTransitiveDigraph (2.2-8)).
The property of Γ being isomorphic to a a split Praeger-Xu graph (IsSplitPraegerXuGraph (2.2-9)).
Now we introduce functions which are used to find information about the library and each of the graphs it stores.
‣ NrCubicVTGraphs( n ) | ( function ) |
‣ NumberCubicVTGraphs( n ) | ( function ) |
Returns: An integer.
Given a positive integer n, this function returns the number of cubic vertex-transitive graphs with n vertices stored in this package.
For any positive integers n up to 1280, the current package stores all cubic vertex-transitive graphs with n vertices.
gap> NrCubicVTGraphs(50);
9
‣ CubicVTGraphId( 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 AllCubicVTGraphs(n) and the ith graph found when iterating through CubicVTGraphIterator(n).
gap> gamma:=CubicVTGraph(8,2);;
gap> CubicVTGraphId(gamma);
2
gap> gamma:=CycleDigraph(8);;
gap> CubicVTGraphId(gamma);
fail
‣ SetCubicVTGraphProps( 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 2.2-1.
CubicVTGraphId (2.2-3).
IsCubicGraph (2.2-6).
IsVertexTransitive (Digraphs: IsVertexTransitive).
gap> gamma:=CompleteDigraph(4);;
gap> SetCubicVTGraphProps(gamma);
gap> IsArcTransitiveDigraph(gamma);
true
‣ SmallCubicVTGraphsInfo( n ) | ( function ) |
Given a positive integer n, this function prints information on the cubic vertex-transitive graphs on n vertices currently stored in this package. This includes the total number of graphs, the enumeration status of these graphs, and the number of graphs with several properties precomputed and stored in this library.
gap> SmallCubicVTGraphsInfo(50);
CVT: There are 9 cubic vertex-transitive graphs on 50 vertices.
Of these 9 graphs, there are;
- 6 bipartite graphs,
- 8 Cayley graphs,
- 1 arc-transitive graphs,
- 0 split Praeger-Xu graphs,
- 9 graphs with solvable automorphism group.
‣ IsCubicGraph( gamma ) | ( property ) |
Returns: true or false.
Given a digraph gamma, this function returns true if gamma is a cubic digraph, and otherwise it returns false.
gap> IsCubicGraph(CycleDigraph(5));
false
gap> IsCubicGraph(CompleteDigraph(4));
true
‣ IsCayleyGraph( gamma ) | ( property ) |
Returns: true or false.
Given a cubic vertex-transitive graph gamma from the GraphSym package such that its properties and attributes have been assigned, this function returns true if gamma is a Cayley (di)graph and false otherwise.
The properties and attributes of a cubic vertex-transitive graph that can be found in the GraphSym package can be assigned using the function SetCubicVTGraphProps (2.2-4), or loaded automatically by the functions CubicVTGraph (2.1-1), AllCubicVTGraphs (2.1-2) or CubicVTGraphIterator (2.1-3). This property is not equivalent to IsCayleyDigraph (Digraphs: IsCayleyDigraph), as a digraph with this property has associated group and generators.
gap> gamma:=CubicVTGraph(50,2,true);;
gap> IsCayleyGraph(gamma);
true
gap> gamma:=CubicVTGraph(50,9,true);;
gap> IsCayleyGraph(gamma);
false
‣ IsArcTransitiveDigraph( gamma ) | ( property ) |
Returns: true or false.
Given a digraph gamma, this function returns true if gamma is arc-transitive and false otherwise. This is a synonym for the function IsEdgeTransitive (Digraphs: IsEdgeTransitive).
gap> gamma:=CubicVTGraph(50,4,true);;
gap> IsArcTransitiveDigraph(gamma);
false
gap> gamma:=CubicVTGraph(50,8,true);;
gap> IsArcTransitiveDigraph(gamma);
true
‣ IsSplitPraegerXuGraph( gamma ) | ( property ) |
Returns: true or false.
Given a cubic vertex-transitive graph gamma from the GraphSym package such that its properties and attributes have been assigned, this function returns true if gamma is a split Praeger-Xu graph and false otherwise.
The properties and attributes of a cubic vertex-transitive graph that can be found in the GraphSym package can be assigned using the function SetCubicVTGraphProps (2.2-4), or loaded automatically by the functions CubicVTGraph (2.1-1), AllCubicVTGraphs (2.1-2) or CubicVTGraphIterator (2.1-3).
gap> gamma:=CubicVTGraph(48,6,true);;
gap> IsSplitPraegerXuGraph(gamma);
false
gap> gamma:=CubicVTGraph(48,7,true);;
gap> IsSplitPraegerXuGraph(gamma);
true
generated by GAPDoc2HTML