Goto Chapter: Top 1 2 3 4 5 Bib Ind

2 Regular graphs

In this chapter we give functions used to identify graphs with various regularity properties and determine their parameters.

2.1 Regular graphs

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$$.

2.1-1 RGParameters
 ‣ 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 ]



2.1-2 IsRG
 ‣ 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



2.1-3 IsFeasibleRGParameters
 ‣ 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



2.2 Edge-regular graphs

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.

2.2-1 ERGParameters
 ‣ 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 ]



2.2-2 IsERG
 ‣ 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



2.2-3 IsFeasibleERGParameters
 ‣ 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



2.3 Strongly regular graphs

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.

2.3-1 SRGParameters
 ‣ 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 ]



2.3-2 IsSRG
 ‣ 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



2.3-3 IsFeasibleSRGParameters
 ‣ 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


Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML