3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ By the way, while it's well known that McLaughlin graph is characterized by its parameters, I'm much less sure about the second graph in question. $\endgroup$
    – Dima Pasechnik
    Commented Jul 13, 2012 at 16:48
  • $\begingroup$ @DimaPasechnik, the uniqueness of the second graph was proved by Kris Coolsaet: projecteuclid.org/euclid.bbms/1136902608 $\endgroup$
    – Anurag
    Commented Feb 5, 2015 at 15:09

3 Answers 3

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ When I try to run the first example in gap it stops with this error in the first line - Variable: 'AtlasGenerators' must have a value. Do you happen to see why? $\endgroup$
    – Jernej
    Commented Feb 9, 2013 at 13:51
  • $\begingroup$ You most probably don't have AtlasRep installed. Try gap> LoadPackage("AtlasRep"); (i.e. one ';', not two - which suppresses output). I guess it will return 'fail'. $\endgroup$
    – Dima Pasechnik
    Commented Feb 10, 2013 at 7:43
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .