Halved Graphs

Author

Eric W. Weisstein
June 11, 2009

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

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

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

Table

Length[l=GraphData[{"Connected","Bipartite"}]]//Timing

l2=Monitor[{#,(
gs=TimeConstrained[HalvedGraphs[Graph[g=#]],10];
If[gs===$Aborted,gs,{gs,FastIsomorphicQ@@gs,RecognizeGraph/@gs}]
)}&/@l,g]

Cases[l2,{_,$Aborted}]

Cases[DeleteCases[l2,{_,$Aborted}],{_,{_,False,_}}][[All,1]]

l1={#[[1]],#[[2,-1,1]]}&/@Cases[DeleteCases[l2,{_,$Aborted}],{_,{_,True,_}}];

Map[GraphData[#,"Name"]&,DeleteCases[l1,{_,{}}|{{_Integer,_Integer}|{"Book"|"Centipede"|"Circulant"|"Cubic"|"CubicPolyhedral"|"CubicTransitive"|"Firecracker"|"Fusene"|"Haar"|"Incidence"|"Ladder"|"Path"|"Polyomino"|"QuarticTransitive"|"Quintic",_}|"SingletonGraph",_}|{_,{_Integer,_Integer}|{"Sextic",_}}],{2}]//TableForm//TraditionalForm