Local McLaughlin Graph

Author

Eric W. Weisstein
November 10, 2010

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/LocalMcLaughlinGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/LocalMcLaughlinGraph.html.

©2010 Wolfram Research, Inc. except for portions noted otherwise

Construction

Neighborhood[g=Graph["McLaughlinGraph"],1,1]

v=NeighborhoodVertices[g,1,1]

Length[v]

g=DeleteVertices[g,v]

RegularParameters[g]

Factor[CharacteristicPolynomial[ToAdjacencyMatrix[g],x]]//TraditionalForm

Spectrum[g]//SpectrumForm//TraditionalForm

RecognizeGraph[g]

Godsil and Royle, p. 232

n=Neighborhood[Graph["McLaughlinGraph"],1,1]

g=DeleteVertices[Graph["McLaughlinGraph"],n]

RecognizeGraph[g]

Flatten[Position[Normal[GetGraphData["McLaughlinGraph","DistanceMatrix"]][[1]],2]]

g=InduceSubgraph[Graph["McLaughlinGraph"],Flatten[Position[Normal[GetGraphData["McLaughlinGraph","DistanceMatrix"]][[1]],2]]]

RecognizeGraph[g]

RegularQ[g]

RegularParameters[g]

IntegerSpectrum[g]//SpectrumForm//TraditionalForm

Is this a local graph?

EgoGraph[g_,i_]:=VertexDelete[NeighborhoodGraph[g,i],i]

g=EgoGraph[GraphData["McLaughlinGraph"],1]

...crashes V8.0.0 kernel...

FastIsomorphicSets[gs=Table[EgoGraph[AdjacencyGraph[GraphData["McLaughlinGraph","AdjacencyMatrix"]],i],{i,GraphData["McLaughlinGraph","V"]}]]//Timing

RecognizeGraph[gs[[1]]]

Edge Coloring

-------- Original Message --------
Subject: LocalMcLaughlin: new small coloring
Date: Wed, 14 Dec 2011 13:02:28 -0600
From: Stan Wagon <wagon@macalester.edu>
To: wendym@csc.uvic.ca, Eric Weisstein <eww@wolfram.com>,        Rob Pratt <Rob.Pratt@sas.com>

Eric computed for me, in half a minute, all the size 15 inde. sets in the LocalMcLaughlin graph. 40000+ of them. And I had the 2200 size-21 ones. 

So here is what I did:

I picked one of the large ones to be in the coloring.
Then I looked only at size-21 sets disjoints from that one and also size-15 sets disjoint from that one. That gave me 11169 sets. 

I ran ISByILP, which is my raw combining of inde. sets by ILP and took merely 153 seconds to find a 10 coloring. I then had to add back to it the first 21-coloring, so in all I have an 11-coloring of this graph.

I realize that some of the 15-sized sets that are not disjoint from the chosen 21-set could be relevant, so this does not disprove a 10-coloring. But it seems as if some combination of thinking and computing might be able to do that. Wendy has disproved 9-coloring...  so I believe chi for this graph is either 10 or 11.

Here is the 11-coloring. 

{1, 4, 4, 3, 3, 7, 1, 2, 3, 2, 1, 4, 4, 10, 1, 1, 1, 2, 7, 3, 2, 11, 11, 11, \
11, 11, 2, 3, 3, 3, 9, 7, 11, 2, 2, 10, 2, 11, 1, 9, 6, 8, 1, 7, 10, 10, 4, \
8, 5, 10, 7, 4, 5, 4, 5, 1, 10, 6, 3, 5, 4, 5, 4, 5, 4, 3, 6, 10, 6, 11, 2, \
10, 6, 1, 10, 7, 2, 11, 4, 4, 5, 2, 7, 7, 3, 5, 1, 3, 10, 10, 10, 5, 1, 2, 7, \
5, 9, 8, 2, 1, 9, 6, 7, 8, 9, 4, 5, 2, 5, 9, 11, 6, 2, 8, 2, 3, 11, 4, 3, 11, \
10, 8, 3, 9, 9, 6, 6, 11, 8, 8, 8, 3, 11, 7, 1, 3, 6, 11, 1, 7, 11, 5, 1, 9, \
2, 1, 1, 11, 6, 7, 1, 7, 11, 7, 1, 4, 10, 11, 1, 4, 11, 11}

Here it is as lists.

{{1, 7, 11, 15, 16, 17, 39, 43, 56, 74, 87, 93, 100, 135, 139, 143, 146, 147, 
  151, 155, 159}, {8, 10, 18, 21, 27, 34, 35, 37, 71, 77, 82, 94, 99, 108, 
  113, 115, 145}, {4, 5, 9, 20, 28, 29, 30, 59, 66, 85, 88, 116, 119, 123, 
  132, 136}, {2, 3, 12, 13, 47, 52, 54, 61, 63, 65, 79, 80, 106, 118, 156, 
  160}, {49, 53, 55, 60, 62, 64, 81, 86, 92, 96, 107, 109, 142}, {41, 58, 67, 
  69, 73, 102, 112, 126, 127, 137, 149}, {6, 19, 32, 44, 51, 76, 83, 84, 95, 
  103, 134, 140, 150, 152, 154}, {42, 48, 98, 104, 114, 122, 129, 130, 
  131}, {31, 40, 97, 101, 105, 110, 124, 125, 144}, {14, 36, 45, 46, 50, 57, 
  68, 72, 75, 89, 90, 91, 121, 157}, {22, 23, 24, 25, 26, 33, 38, 70, 78, 111,
   117, 120, 128, 133, 138, 141, 148, 153, 158, 161, 162}}

I wonder if Rob can attack directly the set of all size-21 and all size-15s as an ILP?  But if not, there must be some good thinning that can be done that would disprove 10 (or find one)

Eric:   For the remaining ones the ind sets might be too large....

coloring={1, 4, 4, 3, 3, 7, 1, 2, 3, 2, 1, 4, 4, 10, 1, 1, 1, 2, 7, 3, 2, 11, 11, 11, 11, 11, 2, 3, 3, 3, 9, 7, 11, 2, 2, 10, 2, 11, 1, 9, 6, 8, 1, 7, 10, 10, 4, 8, 5, 10, 7, 4, 5, 4, 5, 1, 10, 6, 3, 5, 4, 5, 4, 5, 4, 3, 6, 10, 6, 11, 2, 10, 6, 1, 10, 7, 2, 11, 4, 4, 5, 2, 7, 7, 3, 5, 1, 3, 10, 10, 10, 5, 1, 2, 7, 5, 9, 8, 2, 1, 9, 6, 7, 8, 9, 4, 5, 2, 5, 9, 11, 6, 2, 8, 2, 3, 11, 4, 3, 11, 10, 8, 3, 9, 9, 6, 6, 11, 8, 8, 8, 3, 11, 7, 1, 3, 6, 11, 1, 7, 11, 5, 1, 9, 2, 1, 1, 11, 6, 7, 1, 7, 11, 7, 1, 4, 10, 11, 1, 4, 11, 11};

ColoringQ[Graph["LocalMcLaughlinGraph"],coloring]

Options[GraphData["LocalMcLaughlinGraph"]]

SetProperty[GraphData["LocalMcLaughlinGraph"],GraphLayout->Automatic]

System`Graph[EdgeList[GraphData["LocalMcLaughlinGraph"]]]

GraphPlotColoring[System`Graph[EdgeList[GraphData["LocalMcLaughlinGraph"]]],coloring]

GraphData

GraphDataString

Print[GraphDataString[g,
"Name"->"local McLaughlin graph",
"StandardName"->"LocalMcLaughlinGraph",
"Classes"->{"DeterminedBySpectrum"},
TimeConstraint->120,
Debug->True
]]