In this chapter we give functions used to identify graphs with various regularity properties and determine their parameters.
A graph \(\Gamma\) is regular with parameters \((v,k)\) if \(\Gamma\) is simple and undirected, it has order \(v\), and every vertex of \(\Gamma\) 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 \(( \textit{v}, \textit{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\geq 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 \(\Gamma\) 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 \(( \textit{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\geq 0\);
\(2\) divides \(ka\) and \(6\) divides \(vka\);
\(v-2k+a \geq 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 \(\Gamma\) 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 \(( \textit{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\geq b\);
\((v-k-1)b = k(k-a-1)\);
\(v-2-2k+b \geq 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