Chang Graphs

Author

Eric W. Weisstein
August 18, 2012

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

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

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

Enumeration

GraphData["Chang"]

Paramaters

{m(m-1)/2,2(m-2),m-2,4}/.m->8

"StronglyRegular"/.GraphData["Chang","NotationRules"]

Select[GraphData["StronglyRegular"],("StronglyRegular"/.GraphData[#,"NotationRules"])==={28,12,6,4}&]

GraphicsGrid[{GraphData/@Take[%,3]},ImageSize->400]

LCF

{"Chang", 1}

h=HamiltonianCycles[Graph[g={"Chang",1}],10^5];//Timing

Tally[Last/@(lcf=LCF[GraphData[g,"EdgeIndices"],h,All])]//Timing

LCFCycleSearch[{"Chang",1},5 10^5]//Timing

LCFCycleSearch[{"Chang",1},10^6]//Timing

LCFCycleSearch[{"Chang",1},2 10^6]//Timing

{"Chang", 2}

h=HamiltonianCycles[Graph[g={"Chang",2}],10^5];//Timing

Tally[Last/@(lcf=LCF[GraphData[g,"EdgeIndices"],h,All])]//Timing

LCFCycleSearch[{"Chang",2},5 10^5]//Timing

LCFCycleSearch[{"Chang",2},10^6]//Timing

LCFCycleSearch[{"Chang",2},2 10^6]//Timing

{"Chang", 3}

h=HamiltonianCycles[Graph[g={"Chang",3}],10^5];//Timing

Tally[Last/@(lcf=LCF[GraphData[g,"EdgeIndices"],h,All])]//Timing

LCFCycleSearch[{"Chang",3},10^6]//Timing

LCFCycleSearch[{"Chang",3},2 10^6]//Timing

Embeddings

Wikipedia

s=Import["http://upload.wikimedia.org/wikipedia/commons/0/04/Chang_graphs.svg","String"]

StringPosition[s,"<g style=\"stroke:#000040;stroke-width:1.5;stroke-opacity:0.2\">"]

Length[ss=Rest[StringSplit[s,"<g style=\"stroke:#000040;stroke-width:1.5;stroke-opacity:0.2\">"]]]

gs=SVGToGraph/@ss

RecognizeGraph/@%

Append[GraphData[#,{"V","M"}],GraphData[#,"Degrees"]//Union]&/@GraphData["Chang"]

Through[{VertexCount,EdgeCount}[gs[[2]]]]

Union/@VertexDegree/@gs

VertexDegree[gs[[2]]]

Tally[%]

GraphData

Subject

GraphClassString[GraphData["Chang"]]

Construction

distanceregular.org

gs=DistanceRegularGraph["http://www.distanceregular.org/graphdata/chang.am"]

ToEntity/@gs