#############################################################################
##
#W regprop.gi Algebraic Graph Theory package Rhys J. Evans
##
##
#Y Copyright (C) 2020
##
## Implementation file for functions involving regularity properties of
## graphs.
##
#############################################################################
##
#F RGParameters( <gamma> )
##
InstallGlobalFunction( RGParameters,
function( gamma )
local v;
if not IsGraph(gamma) then
Error("usage: RGParameters( <Graph> )");
fi;
if not IsSimpleGraph(gamma) then
return fail;
fi;
if not IsRegularGraph(gamma) then
return fail;
fi;
return [gamma.order, Length(Adjacency(gamma,1))];
end );
#############################################################################
##
#F IsRG( <gamma> )
##
## See GRAPE package function IsRegularGraph
#############################################################################
##
#F IsFeasibleRGParameters( [ <v>, <k> ] )
##
InstallGlobalFunction( IsFeasibleRGParameters,
function( parms )
local v,k;
# Input is list of 2 integers
if not (IsList(parms) and Length(parms)=2 and ForAll(parms,IsInt)) then
Error("usage: IsFeasibleRGParameters( [ <Int>, <Int> ] )");
fi;
v:=parms[1];
k:=parms[2];
# No graphs without vertices or edges
if v=0 then
return false;
fi;
# Basic bounds relating the parameters
if not (k >=0 and v>k) then
return false;
fi;
# Divisibility conditions
if not (2 in DivisorsInt(v*k)) then
return false;
fi;
return true;
end );
#############################################################################
##
#F ERGParameters( <gamma> )
##
InstallGlobalFunction( ERGParameters,
function( gamma )
local v,edges,orbs,reps,e,x,y,adjx,adjy,k,a;
if not IsGraph(gamma) then
Error("usage: ERGParameters( <Graph> )");
fi;
v:=gamma.order;
# The empty graph is not edge-regular
if v=0 then
return fail;
fi;
if not IsSimpleGraph(gamma) then
return fail;
fi;
if not IsRegularGraph(gamma) then
return fail;
fi;
edges := UndirectedEdges(gamma);
# Null graphs are not edge-regular
if edges=[] then
return fail;
fi;
if IsBound(gamma.autGroup) then
orbs:=Orbits(gamma.autGroup,edges,OnSets);
else
orbs:=Orbits(gamma.group,edges,OnSets);
fi;
reps:=orbs{[1..Length(orbs)]}[1];
x := reps[1][1];
adjx := Adjacency(gamma,x);
k:=Length(adjx);
y := reps[1][2];
adjy := Adjacency(gamma,y);
a := Length(Intersection(adjx,adjy));
for e in reps do
x:=e[1];
y:=e[2];
adjx := Adjacency(gamma,x);
adjy := Adjacency(gamma,y);
if not Length(Intersection(adjx,adjy)) = a then
return fail;
fi;
od;
return [v,k,a];
end );
#############################################################################
##
#F IsERG( <gamma> )
##
InstallGlobalFunction( IsERG,
function(gamma)
if not IsGraph(gamma) then
Error("usage: IsERG( <Graph> )");
fi;
if not ERGParameters(gamma)=fail then
return true;
fi;
return false;
end );
#############################################################################
##
#F IsFeasibleERGParameters( [ <v>, <k>, <a> ] )
##
InstallGlobalFunction( IsFeasibleERGParameters,
function( parms )
local v,k,a;
# Input is list of 3 integers
if not (IsList(parms) and Length(parms)=3 and ForAll(parms,IsInt)) then
Error("usage: IsFeasibleERGParameters( [ <Int>, <Int>, <Int> ] )");
fi;
v:=parms[1];
k:=parms[2];
a:= parms[3];
# No graphs without vertices or edges
if v=0 or k=0 then
return false;
fi;
# Basic bounds relating the parameters
if not (a >=0 and k>a and v>k) then
return false;
fi;
# Divisibility conditions
if not (2 in DivisorsInt(v*k)) then
return false;
fi;
if not a=0 then
if not (2 in DivisorsInt(k*a) and 6 in DivisorsInt(v*k*a)) then
return false;
fi;
fi;
# Simple counting argument force the following inequality
if not (v-2*k+a>=0) then
return false;
fi;
return true;
end );
#############################################################################
##
#F SRGParameters( <gamma> )
##
InstallGlobalFunction( SRGParameters,
function( gamma )
local v,eparms,cparms;
v:=gamma.order;
if not IsGraph(gamma) then
Error("usage: SRGParameters( <Graph> )");
fi;
eparms := ERGParameters(gamma);
if eparms=fail then
return fail;
fi;
cparms := ERGParameters(ComplementGraph(gamma));
if cparms=fail then
return fail;
fi;
Add(eparms,v-2*cparms[2]+cparms[3]);
return eparms;
end );
#############################################################################
##
#F IsSRG( <gamma> )
##
InstallGlobalFunction( IsSRG,
function( gamma )
if not IsGraph(gamma) then
Error("usage: IsSRG( <Graph> )");
fi;
if not SRGParameters(gamma)=fail then
return true;
fi;
return false;
end );
#############################################################################
##
#F IsFeasibleSRGParameters( [ <v>, <k>, <a>, <b> ] )
##
InstallGlobalFunction( IsFeasibleSRGParameters,
function( parms )
local v,k,a,b,disc,sqrt,m1;
# Input is list of 4 integers
if not (IsList(parms) and Length(parms)=4 and ForAll(parms,IsInt)) then
Error("usage: IsFeasibleERGParameters( [ <Int>, <Int>, <Int>, <Int> ] )");
fi;
v:=parms[1];
k:=parms[2];
a:=parms[3];
b:=parms[4];
# No graphs without vertices or edges
if v=0 or k=0 then
return false;
fi;
# Basic bounds relating the parameters
if not (a>=0 and k>a and v>k and k>=b) then
return false;
fi;
# Divisibility conditions
if not (2 in DivisorsInt(v*k)) then
return false;
fi;
if not a=0 then
if not (2 in DivisorsInt(k*a) and 6 in DivisorsInt(v*k*a)) then
return false;
fi;
fi;
# Simple counting arguments force the following equality
if not (v-k-1)*b=k*(k-a-1) then
return false;
fi;
# Simple counting arguments force the following inequalities
if not (v-2*k+a>=0 and v-2-2*k+b>=0) then
return false;
fi;
# Integrality of eigenvalue multiplicities
disc:=(a-b)*(a-b)+4*(k-b);
sqrt:=RootInt(disc);
if not (disc=sqrt*sqrt or 2*k+(v-1)*(a-b)=0) then
return false;
fi;
m1:=((v-1)+((2*k+(v-1)*(a-b))/sqrt))/2;
if not IsInt(m1) then
return false;
fi;
return true;
end );
#############################################################################
##
#E
