In this chapter we give functions used to identify graphs with various regularity properties and determine their parameters.
A graph Γ is regular with parameters (v,k) if Γ is simple and undirected, it has order v, and every vertex of Γ has degree k.
‣ RGParameters( gamma ) | ( function ) |
Returns: A list or fail.
Given a graph gamma, this function returns the regular graph parameters of gamma. If gamma is not a regular graph, the function returns fail.
gap> gamma:=EdgeOrbitsGraph(Group((2,3,4,5)),[[1,2],[2,1]]);;
gap> RGParameters(gamma);
fail
gap> gamma:=HammingGraph(3,4);;
gap> RGParameters(gamma);
[ 64, 9 ]
‣ IsRG( gamma ) | ( function ) |
Returns: true or false.
Given a graph gamma, this function returns true if gamma is a regular graph, and false otherwise.
gap> gamma:=NullGraph(Group(()),5);;
gap> IsRG(gamma);
true
gap> gamma:=EdgeOrbitsGraph(Group((2,3,4,5)),[[1,2],[2,1]]);;
gap> IsRG(gamma);
false
gap> gamma:=TriangularGraph(6);;
gap> IsRG(gamma);
true
‣ IsFeasibleRGParameters( [v, k] ) | ( function ) |
Returns: true or false.
Given a list of integers of length 2, [v,k], this function returns true if ( v, k ) is a feasible parameter tuple for a regular graph. Otherwise, the function returns false.
The tuple (v, k) is a feasible parameter tuple for a regular graph if it satisfies the following well-known conditions:
v>k≥ 0;
2 divides vk.
Any regular graph must have parameters that satisfy these conditions (see [BCN89]).
gap> IsFeasibleRGParameters([15,9]);
false
gap> IsFeasibleRGParameters([16,9]);
true
A graph Γ is edge-regular with parameters (v,k,a) if it is regular with parameters (v,k), it has at least one edge, and every pair of adjacent vertices have exactly a common neighbours.
‣ ERGParameters( gamma ) | ( function ) |
Returns: A list or fail.
Given a graph gamma, this function returns the edge-regular graph parameters of gamma. If gamma is not an edge-regular graph, the function returns fail.
gap> gamma:=NullGraph(Group(()),5);;
gap> ERGParameters(gamma);
fail
gap> gamma:=JohnsonGraph(7,3);;
gap> ERGParameters(gamma);
[ 35, 12, 5 ]
‣ IsERG( gamma ) | ( function ) |
Returns: true or false.
Given a graph gamma, this function returns true if gamma is an edge-regular graph, and false otherwise.
gap> gamma:=NullGraph(Group(()),5);;
gap> IsERG(gamma);
false
gap> gamma:=JohnsonGraph(7,3);;
gap> IsERG(gamma);
true
‣ IsFeasibleERGParameters( [v, k, a] ) | ( function ) |
Returns: true or false.
Given a list of integers of length 3, [v,k,a], this function returns true if ( v, k, a ) is a feasible parameter tuple for an edge-regular graph. Otherwise, the function returns false.
The tuple ( v, k, a ) is a feasible parameter tuple for an edge-regular graph if it satisfies the following well-known conditions:
(v,k) is a feasible regular graph parameter tuple;
k>a≥ 0;
2 divides ka and 6 divides vka;
v-2k+a ≥ 0.
Any edge-regular graph must have parameters which satisfy these conditions (see [BCN89]).
gap> IsFeasibleERGParameters([15,9,6]);
false
gap> IsFeasibleERGParameters([16,9,4]);
true
A graph Γ is strongly regular with parameters (v,k,a,b) if it is edge-regular with parameters (v,k,a), it has at least one pair of distinct non-adjacent vertices, and every pair of distinct non-adjacent vertices have exactly b common neighbours.
‣ SRGParameters( gamma ) | ( function ) |
Returns: A list or fail.
Given a graph gamma, this function returns the strongly regular graph parameters of gamma. If gamma is not a strongly regular graph, the function returns fail.
gap> gamma:=CompleteGraph(Group(()),5);;
gap> SRGParameters(gamma);
fail
gap> gamma:=JohnsonGraph(5,3);;
gap> SRGParameters(gamma);
[ 10, 6, 3, 4 ]
‣ IsSRG( gamma ) | ( function ) |
Returns: true or false.
Given a graph gamma, this function returns true if gamma is a strongly regular graph, and false otherwise.
gap> gamma:=CompleteGraph(Group(()),5);;
gap> IsSRG(gamma);
false
gap> gamma:=JohnsonGraph(5,3);;
gap> IsSRG(gamma);
true
‣ IsFeasibleSRGParameters( [v, k, a, b] ) | ( function ) |
Returns: true or false.
Given a list of integers of length 4, [v,k,a,b], this function returns true if ( v, k, a, b ) is a feasible parameter tuple for a strongly regular graph. Otherwise, this function returns false.
The tuple (v,k,a,b) is a feasible parameter tuple for a strongly regular graph if it satisfies the following well-known conditions:
(v,k,a) is a feasible edge-regular graph parameter tuple;
k≥ b;
(v-k-1)b = k(k-a-1);
v-2-2k+b ≥ 0;
the formulae for the multiplicities of the eigenvalues of a strongly regular graph with these parameters evaluate to positive integers (see [BH11]).
Any strongly regular graph must have parameters which satisfy these conditions (see [BCN89]).
gap> IsFeasibleSRGParameters([15,9,4,7]);
false
gap> IsFeasibleSRGParameters([10,3,0,1]);
true
generated by GAPDoc2HTML