how can i construct a strongly regular graph with parameter $(275,112,30,56)$(Mclaughlin Graph), (105,32,4,12)?
I need adjacency matrix of them?
I know they are unique.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityhow can i construct a strongly regular graph with parameter $(275,112,30,56)$(Mclaughlin Graph), (105,32,4,12)?
I need adjacency matrix of them?
I know they are unique.
You can construct the McLaughlin graph using GAP.
gap> LoadPackage("AtlasRep");;
gap> mcl:=Group(AtlasGenerators("McL",1).generators);;
gap> LoadPackage("grape");;
gap> Gr:=NullGraph(mcl);;
gap> AddEdgeOrbit(Gr,[1,2]);;
gap> VertexDegrees(Gr);
[ 112 ]
OK, so that's the 1st graph. For the 2nd graph, one has to take various subgraphs and complements of the 1st one:
gap> GrC:=ComplementGraph(Gr);;
gap> GrC1:=InducedSubgraph(GrC,Adjacency(GrC,1));;
gap> VertexDegrees(GrC1);
[ 105 ]
gap> GrC12:=InducedSubgraph(GrC1,Adjacency(GrC1,1));;
gap> VertexDegrees(GrC12);
[ 72 ]
gap> G2:=ComplementGraph(GrC12);;
gap> VertexDegrees(GrC12);
[ 72 ]
gap> VertexDegrees(G2);
[ 32 ]
gap> GlobalParameters(G2); #indeed, that's the graph you asked for:
[ [ 0, 0, 32 ], [ 1, 4, 27 ], [ 12, 20, 0 ] ]
Printing the adjacency matrices of graphs in GAP is easy too, using IsEdge
function. (But do you really need it? You can work with these graphs directly in GAP
, without much extra trouble.)
There's a picture of the McLaughlin graph on Wikipedia at http://en.wikipedia.org/wiki/Local_McLaughlin_graph. It is useless as shown; but if you click on it then do "View Source" or "Save Image", you get to see its SVG source code, which you can convert to an adjacency matrix.
Here is some code for generating these graphs in SAGE
gap('LoadPackage("design")')
McL = graphs.McLaughlinGraph()
D = designs.projective_plane(4)
flags = [(x,B) for x in D.points() for B in D.blocks() if x in B]
def adj(f,g):
return f[0] != g[0] and f[1] != g[1] and (f[0] in g[1] or g[0] in f[1])
T = Graph([(i,j) for i in range(105) for j in range(i+1,105) if adj(flags[i], flags[j])])
print T.is_strongly_regular(parameters=true)
The graph library in SAGE is pretty good, with a lot of good algorithms already implemented. You should check it out: http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html