Semisymmetric Graph

Author

Eric W. Weisstein
May 16, 2017

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

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

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

Semisymmetric

Connected

Table[Total[Boole[SemisymmetricGraphQ/@ConnectedGraphs[n]]],{n,10}]//Timing

Table[Length@GraphData[{"Connected","Semisymmetric"},n],{n,25}]

Position[%,Except[0,_Integer]]//Flatten

Disconnected

Table[Length@GraphData[{"Disconnected","Semisymmetric"},n],{n,25}]

All

Table[Total[Boole[SemisymmetricGraphQ/@Graphs[n]]],{n,10}]//Timing

Table[Length@GraphData["Semisymmetric",n],{n,25}]

Position[%,Except[0,_Integer]]//Flatten

Regular Bipartite

Length/@(rb=Select[#,RegularQ[#]&&BipartiteQ[#]&]&/@Graphs/@Range[9])//Timing

ShowGraphArray[
Flatten[
Partition[#,8,8,{1,1},{}]&/@Map[RecognizeGraph,rb,{2}],
1],
VertexStyle->Disk[.1],
VertexColor->Red,
AspectRatio->Automatic
]

Enumeration

Length/@(ss=Select[#,SemisymmetricQ]&/@rb)//Timing

Would be semisymmetric except nonregular

SortBy[Complement@@GraphData/@{"EdgeTransitive","VertexTransitive","Regular"},First[Flatten[{#}]]&]

Graphic

V5.2

ShowGraphArray[{FolkmanGraph,GrayGraph}]

V7

TableForm[Sort[GraphData[#,{"V","Name"}]&/@GraphData["Semisymmetric"]],TableDepth->2]

s0=SortBy[GraphData["Semisymmetric"],GraphData[#,"V"]&]

s=Select[s0,GraphData[#,"Embeddings"]=!={}&]

GraphicsGrid[{Show[GraphData[#],PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->110,TextAlignment->Center],BaseStyle->{FontSlant->"Italic"}]&/@s}/.AbsolutePointSize[_]:>AbsolutePointSize[4],ImageSize->400,Spacings->-50]

V8

SortBy[GraphData["Semisymmetric"],GraphData[#,"V"]&]

s=SortBy[Monitor[Select[GraphData[All],GraphData[g=#,"Semisymmetric"]&],g],GraphData[#,"V"]&]

Print[{#,VertexTransitiveQ[GraphData[#]]//Timing,EdgeTransitiveQ[GraphData[#]]//Timing}]&/@Most[s];

Print[{#,EdgeTransitiveQ[Graph[#]]//Timing}]&/@m;

Grid[GraphData[#,{"V","Name"}]&/@s,Dividers->All,Alignment->{{Decimal,Left},Automatic}]//TraditionalForm

nices=Select[s,GraphData[#,"Embeddings"]=!={}&]

GraphicsGrid[Partition[Show[GraphData[#,"Image"],PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->150,TextAlignment->Center],BaseStyle->{FontSlant->"Italic"}]&/@nices,3,3,{1,1},{}]/.AbsolutePointSize[_]:>AbsolutePointSize[4],ImageSize->400,Spacings->{-50,Automatic}]

Checks

Missing

Sort[GraphData[#,{"V","#"}]&/@GraphData["Semisymmetric","Missing"]]

l1=Select[GraphData[{"EdgeTransitive","Regular"}],!GraphData[#,"VertexTransitive"]&]

l2=GraphData["Semisymmetric"]

l1==l2