Complete Bipartite Graph

Author

Eric W. Weisstein
August 2, 2023

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

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

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

Embeddings

<<MathWorld`Graphs`

Cases[GraphData["CompleteBipartite"],_String]

{"CompleteBipartite", {1, 3}} == "ClawGraph"

GraphData[{"CompleteBipartite",{1,3}},"StandardName"]

{"CompleteBipartite", {2, 2}} == "SquareGraph"

GraphData[{"CompleteBipartite",{2,2}},"StandardName"]

{"CompleteBipartite", {2, 3}}

GraphData[{"CompleteBipartite",{2,3}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{2,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{2,3}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{2,3}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{2,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CompleteBipartite",{2,3}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{2,3}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CompleteBipartite",{2,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{2,3}},"Graph","Circular"]//StyleGraphs

Circular construction

CompleteGraph1[2,3,GraphLayout->"CircularEmbedding"]

Planar

GraphData[{"CompleteBipartite",{2,3}},"Planar"]

GraphData[{"CompleteBipartite",{2,3}},"Graph","Planar"]//StyleGraphs

Planar construction

CompleteGraph1[2,3,GraphLayout->"PlanarEmbedding"]

Circular two center

CompleteGraph1[2,3,GraphLayout->"CircularBicenteredEmbedding"]

Circulant

GraphData[{"CompleteBipartite",{2,3}},"Circulant"]

GraphData[{"CompleteBipartite",{2,3}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CompleteBipartite",{2,3}},"Halin"]

GraphData[{"CompleteBipartite",{2,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{2,3}},"LCF"]

GraphData[{"CompleteBipartite",{2,3}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{2,3}},"LCFSignature"]

GraphData[{"CompleteBipartite",{2,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"CompleteBipartite",{2,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{2,3}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{2,3}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{2,3}},"VertexList"],GraphData[{"CompleteBipartite",{2,3}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{2,3}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{2,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{2,3}},"Matchstick"]

GraphData[{"CompleteBipartite",{2,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{2,3}},"Edges"]]

g=CompleteGraph1[2,3,GraphLayout->"3DEmbedding"]

UnitDistanceGraphEmbeddingQ@g

3D All

GraphData[{"CompleteBipartite",{2,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{2,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{2,3}},"Polyhedral"]

GraphData[{"CompleteBipartite",{2,3}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {3, 3}} == "UtilityGraph"

GraphData[{"CompleteBipartite",{3,3}},"StandardName"]

{"CompleteBipartite", {3, 5}}

GraphData[{"CompleteBipartite",{3,5}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{3,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{3,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{3,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{3,5}},"EdgeList"]]

Construction from Mohar and Thomassen 2001

Using the numbering of Glover et al. 1979 for projective planar forbidden topological minors

Construction from Glover et al. 1979

H. Glover, J. Huneke, and C. S. Wang, 103 graphs that are irreducible for the projective plane. J. Combinatorial Theory Ser. B 27 3 (1979).

v={{0,0},{1,0},{2,0},{2,1},{1,1},{0,1},{1/2,1/2},{3/2,1/2}};
g0=Graph[Range[Length[v]],Sort[Sort/@(UndirectedEdge@@@{e[1,2,3,4,5,6,1],e[6,7,2,8,4,7],{6,8},
Sequence@@(curvededges={{2,5},{1,4},{3,6}})})],VertexCoordinates->v,VertexLabels->Automatic]

{3,#}&/@curvededges

g=CurvedEdges[g0,{{3,{2,5}},{3,{1,4}},{3,{3,6}}}]

RecognizeGraph[g]

{CircuitRank[g],VertexCount[g],ReverseSort@VertexDegree[g]}

ProjectivePlanarGraphQ[g,Debug->True]//Timing

v={{0,0},{1,0},{2,0},{2,1},{1,1},{0,1},{1/2,1/2},{3/2,1/2}};
g=Graph[Range[Length[v]],Sort[Sort/@(UndirectedEdge@@@{e[1,2,3,4,5,6,1],e[6,7,2,8,4,7],{6,8},
Sequence@@(curvededges={{2,5},{1,4},{3,6}})})],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

DegenerateGraphEmbeddingQ@g

Default embedding

GraphPlot@RotateGraph[Graph[GraphData[{"CompleteBipartite",{3,5}},"Edges"],GraphLayout->"SpringEmbedding"],Pi/2]

v={{0,0},{1/2,0},{1,0},{1,1/2},{1,1},{0,1},{0,1/2},{1/2,1/2}};
g=Graph[Range[Length[v]],Sort[Sort/@(UndirectedEdge@@@{e[1,2,3,4,5,2],e[8,4,6,7,1,4],e[6,2,8,7,3],{5,7}})],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{3,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CompleteBipartite",{3,5}},"Graph","Degenerate"]

Bilateral

GraphData[{"CompleteBipartite",{3,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{3,5}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"CompleteBipartite",{3,5}}],All][[All,All,1]]]

Planar

GraphData[{"CompleteBipartite",{3,5}},"Planar"]

GraphData[{"CompleteBipartite",{3,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{3,5}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{3,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{3,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{3,5}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{3,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{3,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{3,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{3,5}},"Circulant"]

GraphData[{"CompleteBipartite",{3,5}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CompleteBipartite",{3,5}},"Halin"]

GraphData[{"CompleteBipartite",{3,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CompleteBipartite",{3,5}},"Rigid"]

GraphData[{"CompleteBipartite",{3,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CompleteBipartite",{3,5}},"Flexible"]

GraphData[{"CompleteBipartite",{3,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{3,5}},"LCF"]

GraphData[{"CompleteBipartite",{3,5}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{3,5}},"LCFSignature"]

GraphData[{"CompleteBipartite",{3,5}},"LCFNotations"]

GraphData[{"CompleteBipartite",{3,5}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"CompleteBipartite",{3,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{3,5}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{3,5}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{3,5}},"VertexList"],GraphData[{"CompleteBipartite",{3,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"CompleteBipartite",{3,5}},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{3,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{3,5}},"Matchstick"]

GraphData[{"CompleteBipartite",{3,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{3,5}},"Edges"]]

3D All

GraphData[{"CompleteBipartite",{3,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{3,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{3,5}},"Polyhedral"]

GraphData[{"CompleteBipartite",{3,5}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {3, 6}}

GraphData[{"CompleteBipartite",{3,6}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{3,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{3,6}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{3,6}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{3,6}},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"CompleteBipartite",{3,6}},"Edges"],GraphLayout->"SpringEmbedding"]

v=Join[CirclePoints[6],CirclePoints[1/3,3]];
g=Graph[Range[Length[v]],UndirectedEdge@@@Join@@Table[{i,j},{i,6},{j,7,9}],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

GraphPlot@Annotate[,VertexLabels->None]

v=CirclePoints[9];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,9,8,7,5,3,2,1,8,4,5,6,2,9],{6,8},{2,4},{2,7},{3,8}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

GraphData[{"CompleteBipartite",{3,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CompleteBipartite",{3,6}},"Graph","Degenerate"]

Bilateral

GraphData[{"CompleteBipartite",{3,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{3,6}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CompleteBipartite",{3,6}},"Planar"]

GraphData[{"CompleteBipartite",{3,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{3,6}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{3,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{3,6}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{3,6}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{3,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{3,6}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{3,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@RotateGraph[,-Pi/2]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{3,6}},"Circulant"]

GraphData[{"CompleteBipartite",{3,6}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CompleteBipartite",{3,6}},"Halin"]

GraphData[{"CompleteBipartite",{3,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CompleteBipartite",{3,6}},"Rigid"]

GraphData[{"CompleteBipartite",{3,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CompleteBipartite",{3,6}},"Flexible"]

GraphData[{"CompleteBipartite",{3,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{3,6}},"LCF"]

GraphData[{"CompleteBipartite",{3,6}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{3,6}},"LCFSignature"]

GraphData[{"CompleteBipartite",{3,6}},"LCFNotations"]

GraphData[{"CompleteBipartite",{3,6}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

ComputeRandomLCFNotation[{"CompleteBipartite",{3,6}},2,TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{3,6}}],10^5])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

(gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CompleteBipartite",{3,6}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{3,6}}],All])[[All,2]]]//Timing

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CompleteBipartite",{3,6}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

(gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFEmbedding[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData[{"CompleteBipartite",{3,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{3,6}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{3,6}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{3,6}},"VertexList"],GraphData[{"CompleteBipartite",{3,6}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{3,6}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{3,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{3,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CompleteBipartite",{3,6}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{3,6}}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"CompleteBipartite",{3,6}},"Matchstick"]

GraphData[{"CompleteBipartite",{3,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{3,6}},"Edges"]]

3D All

GraphData[{"CompleteBipartite",{3,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{3,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{3,6}},"Polyhedral"]

GraphData[{"CompleteBipartite",{3,6}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {4, 4}}

Names

GraphData[{"CompleteBipartite",{4,4}},"StandardName"]

GraphData[{"CompleteBipartite",{4,4}},"StandardNames"]

Primary

GraphData[{"CompleteBipartite",{4,4}}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson construction

g=Graph[Range[8],UndirectedEdge@@@{{1,2},{1,3},{1,6},{1,7},{2,4},{2,5},{2,8},{3,4},{3,5},{3,8},{4,6},{4,7},{5,6},{5,7},{6,8},{7,8}},VertexCoordinates->(10^(-4)){{13490,-10548},{13490,-6607},{16274,-13334},{16274,-3820},{20213,-13334},{20213,-3820},{22998,-10548},{22998,-6607}}]

RecognizeGraph@g

All

GraphData[{"CompleteBipartite",{4,4}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{4,4}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{4,4}},"EdgeList"]]

Default embedding

RotateGraph[Graph[GraphData[{"CompleteBipartite",{4,4}},"Edges"],GraphLayout->"SpringEmbedding"],Pi/4+.05]

v=CirclePoints[8];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,4,5,8,1,7,2,3,6,7,5,3,1],e[8,6,4,2,8]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{4,4}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CompleteBipartite",{4,4}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{4,4}},"Graph","Circular"]//StyleGraphs

With[{g=},Show[{Graphics[{Blue,Circumsphere[GraphEmbedding@g]}],g}]]

Planar

GraphData[{"CompleteBipartite",{4,4}},"Planar"]

GraphData[{"CompleteBipartite",{4,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{4,4}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{4,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{4,4}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{4,4}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{4,4}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{4,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@RotateGraph[,-Pi/2]

v={{-1,0},{1,0},{0,Sqrt[3]},{-1/4,1/4},{1/4,1/4},{-1/4,1/2},{1/4,1/2},{0,1}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,6,8,7,4,2,3,1,4,6,3,7,5,2,8,1]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{4,4}},"Circulant"]

GraphData[{"CompleteBipartite",{4,4}},"Graph","Circulant"]//StyleGraphs

Circulant construction

CirculantGraph1@@@CirculantIndices[GraphData[{"CompleteBipartite",{4,4}}]]

Halin

GraphData[{"CompleteBipartite",{4,4}},"Halin"]

GraphData[{"CompleteBipartite",{4,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CompleteBipartite",{4,4}},"Rigid"]

GraphData[{"CompleteBipartite",{4,4}},"Graph","Rigid"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{4,4}},"LCF"]

GraphData[{"CompleteBipartite",{4,4}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{4,4}},"LCFSignature"]

GraphData[{"CompleteBipartite",{4,4}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CompleteBipartite",{4,4}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{4,4}}],All])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}]

Length[gs]

UnitDistance

GraphData[{"CompleteBipartite",{4,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{4,4}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{4,4}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{4,4}},"VertexList"],GraphData[{"CompleteBipartite",{4,4}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{4,4}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{4,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{4,4}},"Matchstick"]

GraphData[{"CompleteBipartite",{4,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{4,4}},"Edges"]]

top={2,6,8,4};
bot={1,5,7,3};
v=Tuples[{0,1},3];
g=Graph[Range[8],UndirectedEdge@@@Join[Partition[top,2,1,1],Partition[bot,2,1,1],Transpose[{bot,RotateLeft@top}],Transpose[{bot,RotateRight@top}]],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

3D All

GraphData[{"CompleteBipartite",{4,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{4,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{4,4}},"Polyhedral"]

GraphData[{"CompleteBipartite",{4,4}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {5, 5}}

GraphData[{"CompleteBipartite",{5,5}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{5,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{5,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{5,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{5,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CompleteBipartite",{5,5}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{5,5}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CompleteBipartite",{5,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{5,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CompleteBipartite",{5,5}},"Planar"]

GraphData[{"CompleteBipartite",{5,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{5,5}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{5,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{5,5}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{5,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{5,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{5,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{5,5}},"Circulant"]

GraphData[{"CompleteBipartite",{5,5}},"Graph","Circulant"]//StyleGraphs

Circulant construction

CirculantGraph1@@@CirculantIndices[GraphData[{"CompleteBipartite",{5,5}}],All]

Halin

GraphData[{"CompleteBipartite",{5,5}},"Halin"]

GraphData[{"CompleteBipartite",{5,5}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{5,5}},"LCF"]

GraphData[{"CompleteBipartite",{5,5}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{5,5}},"LCFSignature"]

GraphData[{"CompleteBipartite",{5,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFFromEmbedding[#][[2]]&/@%]

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CompleteBipartite",{5,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{5,5}}],All])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}]

UnitDistance

GraphData[{"CompleteBipartite",{5,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{5,5}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{5,5}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{5,5}},"VertexList"],GraphData[{"CompleteBipartite",{5,5}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{5,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{5,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{5,5}},"Matchstick"]

GraphData[{"CompleteBipartite",{5,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{5,5}},"Edges"]]

3D All

GraphData[{"CompleteBipartite",{5,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{5,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{5,5}},"Polyhedral"]

GraphData[{"CompleteBipartite",{5,5}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {6, 6}}

GraphData[{"CompleteBipartite",{6,6}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{6,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{6,6}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{6,6}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{6,6}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CompleteBipartite",{6,6}},"Edges"]

RegionIntersection[Line[v[[{3,7}]]],Line[v[[{4,8}]]]]//FullSimplify

v=Join[CirclePoints[10],{0,#(Sqrt[1-(2/(Sqrt[5]))])}&/@{-1,1}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,3,5,7,10,2,5,9,11,3,12,7,11,2,1,9,6,2,12,9,10,3,6,7,1,4,6,8,10,4,11,8,12,4,5,8,1]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{6,6}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CompleteBipartite",{6,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{6,6}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CompleteBipartite",{6,6}},"Planar"]

GraphData[{"CompleteBipartite",{6,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{6,6}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{6,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{6,6}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{6,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,250}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{6,6}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{6,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{6,6}},"Circulant"]

GraphData[{"CompleteBipartite",{6,6}},"Graph","Circulant"]//StyleGraphs

Circulant construction

CirculantGraph1@@@CirculantIndices[GraphData[{"CompleteBipartite",{6,6}}]]

Halin

GraphData[{"CompleteBipartite",{6,6}},"Halin"]

GraphData[{"CompleteBipartite",{6,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{6,6}},"LCF"]

GraphData[{"CompleteBipartite",{6,6}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{6,6}},"LCFSignature"]

GraphData[{"CompleteBipartite",{6,6}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CompleteBipartite",{6,6}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{6,6}}],All])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

UnitDistance

GraphData[{"CompleteBipartite",{6,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{6,6}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{6,6}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{6,6}},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{6,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{6,6}},"Matchstick"]

GraphData[{"CompleteBipartite",{6,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{6,6}},"Edges"]]

3D All

GraphData[{"CompleteBipartite",{6,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{6,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{6,6}},"Polyhedral"]

GraphData[{"CompleteBipartite",{6,6}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {7, 7}}

GraphData[{"CompleteBipartite",{7,7}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{7,7}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{7,7}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{7,7}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{7,7}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CompleteBipartite",{7,7}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{7,7}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CompleteBipartite",{7,7}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{7,7}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CompleteBipartite",{7,7}},"Planar"]

GraphData[{"CompleteBipartite",{7,7}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{7,7}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{7,7}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{7,7}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{7,7}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{7,7}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{7,7}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{7,7}},"Circulant"]

GraphData[{"CompleteBipartite",{7,7}},"Graph","Circulant"]//StyleGraphs

Circulant construction

gs=CirculantGraph1@@@CirculantIndices[GraphData[{"CompleteBipartite",{7,7}}]]

Halin

GraphData[{"CompleteBipartite",{7,7}},"Halin"]

GraphData[{"CompleteBipartite",{7,7}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{7,7}},"LCF"]

GraphData[{"CompleteBipartite",{7,7}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{7,7}},"LCFSignature"]

GraphData[{"CompleteBipartite",{7,7}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CompleteBipartite",{7,7}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{7,7}}],All])[[All,2]]]//Timing

Length[gs]

UnitDistance

GraphData[{"CompleteBipartite",{7,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{7,7}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{7,7}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{7,7}},"VertexList"],GraphData[{"CompleteBipartite",{7,7}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{7,7}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{7,7}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{7,7}},"Matchstick"]

GraphData[{"CompleteBipartite",{7,7}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{7,7}},"Edges"]]

3D All

GraphData[{"CompleteBipartite",{7,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{7,7}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{7,7}},"Polyhedral"]

GraphData[{"CompleteBipartite",{7,7}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {8, 8}}

GraphData[{"CompleteBipartite",{8,8}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{8,8}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{8,8}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{8,8}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{8,8}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CompleteBipartite",{8,8}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{8,8}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CompleteBipartite",{8,8}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{8,8}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CompleteBipartite",{8,8}},"Planar"]

GraphData[{"CompleteBipartite",{8,8}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{8,8}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{8,8}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{8,8}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{8,8}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{8,8}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{8,8}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{8,8}},"Circulant"]

GraphData[{"CompleteBipartite",{8,8}},"Graph","Circulant"]//StyleGraphs

Circulant construction

gs=CirculantGraph1@@@CirculantIndices[GraphData[{"CompleteBipartite",{8,8}}]]

Halin

GraphData[{"CompleteBipartite",{8,8}},"Halin"]

GraphData[{"CompleteBipartite",{8,8}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{8,8}},"LCF"]

GraphData[{"CompleteBipartite",{8,8}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{8,8}},"LCFSignature"]

GraphData[{"CompleteBipartite",{8,8}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CompleteBipartite",{8,8}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{8,8}}],All])[[All,2]]]//Timing

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CompleteBipartite",{8,8}},".m.gz"]])[[All,2]]]//Timing

UnitDistance

GraphData[{"CompleteBipartite",{8,8}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{8,8}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{8,8}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{8,8}},"VertexList"],GraphData[{"CompleteBipartite",{8,8}},"EdgeList"]]]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{8,8}},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{8,8}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{8,8}},"Matchstick"]

GraphData[{"CompleteBipartite",{8,8}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{8,8}},"Edges"]]

3D All

GraphData[{"CompleteBipartite",{8,8}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{8,8}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{8,8}},"Polyhedral"]

GraphData[{"CompleteBipartite",{8,8}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {9, 9}}

GraphData[{"CompleteBipartite",{9,9}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{9,9}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{9,9}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{9,9}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{9,9}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CompleteBipartite",{9,9}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{9,9}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CompleteBipartite",{9,9}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{9,9}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CompleteBipartite",{9,9}},"Planar"]

GraphData[{"CompleteBipartite",{9,9}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{9,9}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{9,9}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{9,9}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{9,9}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{9,9}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{9,9}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{9,9}},"Circulant"]

GraphData[{"CompleteBipartite",{9,9}},"Graph","Circulant"]//StyleGraphs

Circulant construction

gs=CirculantGraph1@@@CirculantIndices[GraphData[{"CompleteBipartite",{9,9}}]]

Halin

GraphData[{"CompleteBipartite",{9,9}},"Halin"]

GraphData[{"CompleteBipartite",{9,9}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{9,9}},"LCF"]

GraphData[{"CompleteBipartite",{9,9}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{9,9}},"LCFSignature"]

GraphData[{"CompleteBipartite",{9,9}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CompleteBipartite",{9,9}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{9,9}}],All])[[All,2]]]//Timing

UnitDistance

GraphData[{"CompleteBipartite",{9,9}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{9,9}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{9,9}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{9,9}},"VertexList"],GraphData[{"CompleteBipartite",{9,9}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{9,9}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{9,9}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{9,9}},"Matchstick"]

GraphData[{"CompleteBipartite",{9,9}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{9,9}},"Edges"]]

3D All

GraphData[{"CompleteBipartite",{9,9}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{9,9}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{9,9}},"Polyhedral"]

GraphData[{"CompleteBipartite",{9,9}},"Graph",{"3D","Polyhedron"}]

{"CompleteBipartite", {10, 10}}

GraphData[{"CompleteBipartite",{10,10}},"StandardName"]

Primary

GraphData[{"CompleteBipartite",{10,10}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CompleteBipartite",{10,10}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"CompleteBipartite",{10,10}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"CompleteBipartite",{10,10}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CompleteBipartite",{10,10}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CompleteBipartite",{10,10}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"CompleteBipartite",{10,10}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CompleteBipartite",{10,10}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CompleteBipartite",{10,10}},"Planar"]

GraphData[{"CompleteBipartite",{10,10}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CompleteBipartite",{10,10}},{"RCN","CN"}]

GraphData[{"CompleteBipartite",{10,10}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"CompleteBipartite",{10,10}}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{10,10}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"CompleteBipartite",{10,10}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"CompleteBipartite",{10,10}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CompleteBipartite",{10,10}},"Circulant"]

GraphData[{"CompleteBipartite",{10,10}},"Graph","Circulant"]//StyleGraphs

Circulant construction

gs=CirculantGraph1@@@CirculantIndices[GraphData[{"CompleteBipartite",{10,10}}]]

Halin

GraphData[{"CompleteBipartite",{10,10}},"Halin"]

GraphData[{"CompleteBipartite",{10,10}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CompleteBipartite",{10,10}},"LCF"]

GraphData[{"CompleteBipartite",{10,10}},"HamiltonianCycleCount"]

GraphData[{"CompleteBipartite",{10,10}},"LCFSignature"]

GraphData[{"CompleteBipartite",{10,10}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CompleteBipartite",{10,10}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CompleteBipartite",{10,10}}],All])[[All,2]]]//Timing

UnitDistance

GraphData[{"CompleteBipartite",{10,10}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CompleteBipartite",{10,10}}],Debug->True]//Timing

GraphData[{"CompleteBipartite",{10,10}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CompleteBipartite",{10,10}},"VertexList"],GraphData[{"CompleteBipartite",{10,10}},"EdgeList"]]]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]]]&/@Complement@@(GraphData[{"CompleteBipartite",{10,10}},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"CompleteBipartite",{10,10}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"CompleteBipartite",{10,10}},"Matchstick"]

GraphData[{"CompleteBipartite",{10,10}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CompleteBipartite",{10,10}},"Edges"]]

3D All

GraphData[{"CompleteBipartite",{10,10}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CompleteBipartite",{10,10}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CompleteBipartite",{10,10}},"Polyhedral"]

GraphData[{"CompleteBipartite",{10,10}},"Graph",{"3D","Polyhedron"}]

Checks

DeleteCases[Monitor[{g=#,GraphData[#,"CompleteBipartite"],CompleteBipartiteGraphQ[GraphData[#]]}&/@GraphData[All],g],{_,x_,x_}]//Timing

Examples

Built-in

GraphicsRow[System`CompleteGraph[#,VertexSize->{"Scaled",.04},System`VertexStyle->Red,System`EdgeStyle->Black]&/@{{3,2},{2,5}}]

Combinatorica

ShowGraphArray[Combinatorica`CompleteGraph@@@{{3,2},{2,5}}]

Foucault's Pendulum

Built-in

System`CompleteGraph[{18,18},AspectRatio->.8]

Legacy

GraphPlot[CompleteGraph[18,18],Method->None,AspectRatio->.8]

Planar

Table[GraphData[{"CompleteBipartite",{2,n}}],{n,2,10}]

RecognizeGraph/@%

GraphData["K2,5","Graph","All"]

GraphData["K2,8","Graph","Planar"]

GraphData["K2,7","Graph","Planar"]

GraphData["K2,7","Embeddings"][[2]]

Clear[CompleteBipartitePlanar]

CompleteBipartitePlanar[2,n_,opts___?OptionQ]:=System`Graph[
Range[n+2],
UndirectedEdge@@@Join[{},Flatten[Table[{{1,i+2},{2,i+2}},{i,n}],1]],VertexCoordinates->Join[{{0,-1},{0,1}},Table[{2i/(n-1),0},{i,-(n-1)/2,(n-1)/2}]],
opts
]

Range[-2/2,2/2]

Range[-7/2,7/2]

CompleteBipartitePlanar[2,7,VertexLabels->"Name"]

Table[CompleteBipartitePlanar[2,n],{n,2,20}]

RecognizeGraph/@%

GraphData["K2,10"]

Properties m×n

Acyclic

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{True,Min[m,n]==1}},False],GraphData[#,"Acyclic"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

AdjacencyMatrixCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Multinomial[m,n]/Piecewise[{{2,m==n}},1],GraphData[#,"AdjacencyMatrixCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Multinomial[n,n]

Arboricity

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Ceiling[((m n)/(m+n-1))],GraphData[#,"Arboricity"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ArcTransitive

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{True,m==n}},False],GraphData[#,"ArcTransitive"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ArcTransitivity

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{1,m==n==1},{Infinity,m==n==2},{3,m==n}},Missing["NotApplicable"]],GraphData[#,"ArcTransitivity"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

AutomorphismCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2m!n!,m==n}},m!n!],GraphData[#,"AutomorphismCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

BalabanIndex

Entity["Graph",{"CompleteBipartite",{n,n}}]["BalabanIndex"]

FullSimplify[(((m^2) (n^2))/((2+m (-1+n)-n) (Sqrt[(-2+2 m+n) (-2+m+2 n)])))/.m->n,n>0&&n∈Integers]//Factor

Table[GraphData[{"CompleteBipartite",{m,n}},"BalabanIndex"]^2,{n,20},{m,n}]//Column

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(((m^2) (n^2))/((2+m (-1+n)-n) (Sqrt[(-2+2 m+n) (-2+m+2 n)]))),GraphData[#,"BalabanIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

mn=MapIndexed[Factor@FindSequenceFunction[#,n-#2[[1]]]&,Table[GraphData[{"CompleteBipartite",{n,m}},"BalabanIndex"]^2,{n,2,11},{m,n,20}]]

FindSequenceFunction[mn,m-1]//Factor

Table[(((m^4) (n^4))/((-2+2 m+n) (-2+m+2 n) (((2-m-n+m n))^2))),{m,9}]

FullSimplify[(Sqrt[(((m^4) (n^4))/((-2+2 m+n) (-2+m+2 n) (((2-m-n+m n))^2)))]),m>0&&n>0&&(m|n)∈Integers]

Bandwidth

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Floor[(Max[m,n]-1)/2]+Min[m,n],GraphData[#,"Bandwidth"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

BridgeCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{Max[m,n],Min[m,n]==1}},0],GraphData[#,"BridgeCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

BurningNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2,Min[m,n]<3}},3],GraphData[#,"BurningNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CharacteristicPolynomial

DeleteCases[{#1,FullSimplify[#2/#3]}&@@@(Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],((#^2-m n) #^(m+n-2)&)[x],GraphData[#,"CharacteristicPolynomial"][x]}]&/@GraphData["CompleteBipartite"]),{_,-1|1}]

ChordCount

Entity["Graph",{"CompleteBipartite",{n,n}}]["ChordCount"]

Entity["Graph",{"CompleteBipartite",{m,n}}]["ChordCount"]

Chords[GraphData["K3,11"]]

Length[%]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]<3}},m n],GraphData[#,"ChordCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ChordlessCycleCount

Entity["Graph",{"CompleteBipartite",{n,n}}]["ChordlessCycleCount"]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Binomial[m,2]Binomial[n,2],GraphData[#,"ChordlessCycleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ChromaticInvariant

A291774

Entity["Graph",{"CompleteBipartite",{n,n}}]["ChromaticInvariant"]

Table[GraphData[{"CompleteBipartite",Sort[{m,n}]},"ChromaticInvariant"],{n,20},{m,n}]//Column

Table[GraphData[{"CompleteBipartite",Sort[{m,n}]},"ChromaticInvariant"],{n,10},{m,n}]//Flatten

Join[{1},Table[Sum[k!(((-1))^(k+m))(((k+1))^n)StirlingS2[m,k+2],{k,0,m-1}],{n,2,10},{m,n}]]//Flatten

Table[Piecewise[{{1,m==n==1}},Sum[k!(((-1))^(k+Min[m,n]))(((k+1))^(Max[m,n]))StirlingS2[Min[m,n],k+2],{k,0,Min[m,n]-1}]],{n,20},{m,n}]//Column

DeleteCases[Block[{m,n},{
{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],
Piecewise[{{1,m==n==1}},Sum[k!(((-1))^(k+Min[m,n]))(((k+1))^(Max[m,n]))StirlingS2[Min[m,n],k+2],{k,0,Min[m,n]-1}]],
GraphData[#,"ChromaticInvariant"]
}]&/@GraphData["CompleteBipartite"],
{_,x_,x_}]

deletefromfirstmissing[l_]:=Take[l,FirstPosition[l,_Missing,{Length[l]+1}][[1]]-1]

(mn=MapIndexed[Factor@FindSequenceFunction[deletefromfirstmissing@#,n-1]&,Table[GraphData[{"CompleteBipartite",Sort[{n,m}]},"ChromaticInvariant"],{n,2,11},{m,2,20}]])//Column

{
1,
-3+(2^n),
7-6 (2^n)+2 (3^n),
-15+25 (2^n)-20 (3^n)+6 (4^( n)),
31-90 (2^n)+130 (3^n)-90 (4^( n))+24 (5^n),
-63+301 (2^n)-700 (3^n)+840 (4^n)-504 (5^n)+120 (6^n)
}

Table[StirlingS2[n,1],{n,10}]

Table[StirlingS2[n,2],{n,10}]

Table[StirlingS2[n,3],{n,10}]

2!Table[StirlingS2[n,4],{n,10}]

3!Table[StirlingS2[n,5],{n,10}]

Table[Sum[k!(((-1))^(k+m))(((k+1))^n)StirlingS2[m,k+2],{k,0,m-1}],{n,5},{m,n}]

Sum[k!(((-1))^(k+m))(((k+1))^n)StirlingS2[m,k+2],{k,0,m-1}]

(r=MapIndexed[FindLinearRecurrence[deletefromfirstmissing@#]&,Table[GraphData[{"CompleteBipartite",Sort[{n,m}]},"ChromaticInvariant"],{n,11},{m,2,20}]])//Column

-Rest/@Table[StirlingS1[n,n+1-k],{n,10},{k,n}]//Column

ChromaticNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],2,GraphData[#,"ChromaticNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ChromaticPolynomial

Table[GraphData[{"CompleteBipartite",Sort[{m,n}]},"ChromaticPolynomial"][x],{n,5},{m,n}]//Column

Table[Factor/@Piecewise[{{1,m==n==1}},x(x-1)Sum[(x^(k+1))k!(((-1))^(k+Min[m,n]))(((k+1))^(Max[m,n]))StirlingS2[Min[m,n],k+2],{k,0,Min[m,n]-1}]],{n,5},{m,n}]//Column

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"ChromaticPolynomial"][x]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Take[poly,5]//Expand//Column

coef=Factor/@FindLinearRecurrence[(poly/(x(x-1)))]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

Circumference

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2 Min[m,n],Min[m,n]>1}},Missing["NotApplicable"]],GraphData[#,"Circumference"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Classes

new=Intersection@@(GraphData[#,"Classes"]&/@GraphData["CompleteBipartite"])

CliqueCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(m+1)(n+1),GraphData[#,"CliqueCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CliqueCoveringNumber

Entity["Graph",{"CompleteBipartite",{m,n}}]["CliqueCoveringNumber"]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Max[m,n],GraphData[#,"CliqueCoveringNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CliqueNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],2,GraphData[#,"CliqueNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CliquePolynomial

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[((m #+1) (n #+1)&)[x]-GraphData[#,"CliquePolynomial"][x]]}]&/@GraphData["CompleteBipartite"],{_,0}]

ComplementOddChordlessCycleCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],0,GraphData[#,"ComplementOddChordlessCycleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ConnectedComponentCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],1,GraphData[#,"ConnectedComponentCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ConnectedDominatingSetCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{3,m==n==1},{2^Max[m,n],Min[m,n]==1}},(2^m-1) (2^n-1)],GraphData[#,"ConnectedDominatingSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ConnectedDominationNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{1,Min[m,n]==1}},2],GraphData[#,"ConnectedDominationNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ConnectedDominationPolynomial

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[Piecewise[{{2 x+x^2,m==n==1},{x+((x+1)^m-1) ((x+1)^n-1),Min[m,n]==1}},((x+1)^m-1) ((x+1)^n-1)]-GraphData[#,"ConnectedDominationPolynomial"][x]]}]&/@GraphData["CompleteBipartite"],{_,0}]

ConnectedInducedSubgraphCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(2^m-1) (2^n-1)+m+n,GraphData[#,"ConnectedInducedSubgraphCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ConnectedInducedSubgraphPolynomial

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[((x+1)^m-1) ((x+1)^n-1)+(m+n) x-GraphData[#,"ConnectedInducedSubgraphPolynomial"][x]]}]&/@GraphData["CompleteBipartite"],{_,0}]

CrossingNumber

A030179 (conjectured)

Conjectured to be crossing number of complete bipartite graph K_{m,n}.

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Floor[n/2]Floor[(n-1)/2]Floor[m/2]Floor[(m-1)/2],GraphData[#,"CrossingNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CycleCount

Entity["Graph",{"CompleteBipartite",{m,n}}]["CycleCount"]

{n,n}: 1/2 Sum[\[FormalK]! (\[FormalK]-1)! Binomial[n,\[FormalK]]^2,{\[FormalK],2,n}]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],1/2 Sum[k! l! Binomial[m,k]Binomial[n,l],{k,2,m},{l,2,n}],GraphData[#,"CycleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{m,n}},"CycleCount"],{n,10},{m,n}]//Column

Table[GraphData[{"CompleteBipartite",{2,n}},"CycleCount"],{n,2,10}]

FindSequenceFunction[%,n-1]

Table[GraphData[{"CompleteBipartite",{3,n}},"CycleCount"],{n,3,10}]

FindSequenceFunction[%,n-2]//FullSimplify

Table[GraphData[{"CompleteBipartite",{4,n}},"CycleCount"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

CyclePolynomial

Entity["Graph",{"CompleteBipartite",{m,n}}]["CyclePolynomial"]

(poly=Table[GraphData[{"CompleteBipartite",Sort[{m,n}]},"CyclePolynomial"],{n,20},{m,20}]/.f_Function:>f[x])//Column

Take[poly,4]//Column

FindSequenceFunction[DeleteMissing@#,n]&/@Take[poly,5]//Factor//Column

FindLinearRecurrence[DeleteMissing@#]&/@Take[poly,3]

FindLinearRecurrence[DeleteMissing@#]&/@Take[poly,5]

Table[(((-1))^(k+1))Binomial[n,k],{n,10},{k,n}]

RSolve[{a[n]==3a[n-1]-3a[n-2]+a[n-3],a[1]==0,a[2]==(x^4),a[3]==3(x^4)},a[n],n]

RSolve[{a[n]==4a[n-1]-6a[n-2]+4a[n-3]-a[n-4],a[1]==0,a[2]==3(x^4),a[3]==9 (x^4)+6 (x^6),a[4]==18 (x^4)+24 (x^6)},a[n],n]//Factor

Cyclic

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{False,Min[m,n]==1}},True],GraphData[#,"Cyclic"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CyclomaticNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(m-1)(n-1),GraphData[#,"CyclomaticNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

DetourIndex

Entity["Graph",{"CompleteBipartite",{n,n}}]["DetourIndex"]

{n,n}: n (2-5 n+4 (n^2))

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"DetourIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

mn=MapIndexed[Factor@FindSequenceFunction[DeleteMissing@#,n-#2[[1]]]&,Table[GraphData[{"CompleteBipartite",{n,m}},"DetourIndex"],{n,2,11},{m,n,20}]]

mn=MapIndexed[Factor@FindLinearRecurrence[DeleteMissing@#]&,Table[GraphData[{"CompleteBipartite",{n,m}},"DetourIndex"],{n,2,11},{m,n,20}]]

FindSequenceFunction[mn,m-1]//Factor

DetourMatrix

GraphData[{"CompleteBipartite",{2,2}},"#"]

MatrixForm/@(d1=Table[GraphData[{"CompleteBipartite",{n,n}},"DetourMatrix"],{n,5}])

MatrixForm/@(d2=Table[SparseArray[{{i_,i_}->0,{i_,j_}/;((i≤n&&j≤n)||(i>n&&j>n))->2 n-2},2 n,2 n-1],{n,5}])

d1-d2

DetourPolynomial

{n,n}: (((-2+2 n+x))^(-2+2 n)) (-2+3 n+x) (-2+5 n-4 (n^2)+x)

Diameter

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{1,m==n==1}},2],GraphData[#,"Diameter"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

DistanceMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"DistanceMatrix"],{n,5}]

MatrixForm/@Table[With[{z=ConstantArray[2,n {1,1}],o=ConstantArray[1,n {1,1}]},ArrayFlatten[{{z,o},{o,z}}]]-2 IdentityMatrix[2 n],{n,5}]

DistancePolynomial

{n,n}: (((2+x))^(-2+2 n)) (2-3 n+x) (2-n+x)

DistinguishingNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{n+1,m==n}},Max[m,n]],GraphData[#,"DistinguishingNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

DomaticNumber m×n

Block[{m,n},Sort[{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"DomaticNumber"],Piecewise[{{2,Min[m,n]==1}},Min[m,n]]}&/@GraphData["CompleteBipartite"]]]

DeleteCases[%,{_,x_,x_}]

DominatingSetCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],3-(2^m)-(2^n)+(2^(m+n)),GraphData[#,"DominatingSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

FindSequenceFunction[seq,n]//FullSimplify

Table[GraphData[{"CompleteBipartite",{2,n}},"DominatingSetCount"],{n,2,10}]

FindSequenceFunction[%,n-1]

Table[GraphData[{"CompleteBipartite",{3,n}},"DominatingSetCount"],{n,3,10}]

FindSequenceFunction[%,n-2]

Table[GraphData[{"CompleteBipartite",{4,n}},"DominatingSetCount"],{n,4,10}]

FindSequenceFunction[%,n-3]

Table[GraphData[{"CompleteBipartite",{5,n}},"DominatingSetCount"],{n,5,10}]

FindSequenceFunction[%,n-4]

Sum[2^k,{k,n}]

{4,8m,16

Table[2 (1-(2^(m-1)))+1,{m,2,5}]

Table[3+2 (m-1)(m-2),{m,2,5}]

Table[2 (1-(2^(m-1)))+1+(-2 (1-(2^(m-1)))+1)2^n,{m,2,5}]

Table[2 (1-(2^(m-1)))+1+(-2 (1-(2^(m-1)))+1)2^n,{n,2,10},{m,2,10}]

Simplify[2 (1-(2^(m-1)))+1]

Simplify[(-2 (1-(2^(m-1)))+1)]

Expand[3-(2^m)+((2^m)-1)(2^n)]

DominationNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{1,Min[m,n]==1}},2],GraphData[#,"DominationNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

DominationPolynomial

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[(((1+#)^m-1) ((1+#)^n-1)+#^m+#^n&)[x]-GraphData[#,"DominationPolynomial"][x]]}]&/@GraphData["CompleteBipartite"],{_,0}]

EdgeChromaticNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Max[m,n],GraphData[#,"EdgeChromaticNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

EdgeConnectivity

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Min[m,n],GraphData[#,"EdgeConnectivity"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

EdgeCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],m n,GraphData[#,"EdgeCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

EdgeCoverCount

{n,n}:

Sum[(((-1))^k)Binomial[n,k](2^((n-k)n))(((1-(2^(k-n))))^n),{k,0,n}]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],m n,GraphData[#,"EdgeCoverCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

EdgeCoverNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Max[m,n],GraphData[#,"EdgeCoverNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

EdgeCoverPolynomial

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[(Sum[(-1)^\[FormalK] Binomial[m,\[FormalK]] ((#+1)^(m-\[FormalK])-1)^n,{\[FormalK],0,m}]&)[x]-GraphData[#,"EdgeCoverPolynomial"][x]]}]&/@GraphData["CompleteBipartite"],{_,0}]

EulerianCycleCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{0,Mod[m,2]==1||Mod[n,2]==1}},Missing["NotAvailable"]],GraphData[#,"EulerianCycleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

FaceCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{1,m==n==2},{0,Min[m,n]==1},{Max[m,n],Min[m,n]==2}},Missing["NotApplicable"]],GraphData[#,"FaceCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

FibonacciCube

Entity["Graph",{"CompleteBipartite",{m,n}}]["FibonacciCube"]

GraphData[#,"NotationRules","CompleteBipartite"]&/@GraphData[{"CompleteBipartite","FibonacciCube"}]

FlowPolynomial

FractionalChromaticNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],2,GraphData[#,"FractionalChromaticNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

FractionalEdgeChromaticNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Max[m,n],GraphData[#,"FractionalEdgeChromaticNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Girth

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{Infinity,m==1||n==1}},4],GraphData[#,"Girth"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Gonality

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Min[m,n],GraphData[#,"Gonality"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

HamiltonConnected

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{True,m==n==1}},False],GraphData[#,"HamiltonConnected"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

HamiltonDecompositionCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{Missing["NotAvailable"],m>1&&m==n}},Missing["NotApplicable"]],GraphData[#,"HamiltonDecompositionCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Hamiltonian

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{True,m>1&&m==n}},False],GraphData[#,"Hamiltonian"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

HamiltonianCycleCount

{n,n}: n! (n-1)!/2,

Entity["Graph",{"CompleteBipartite",{n,n}}]["HamiltonianCycleCount"]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{n! (n-1)!/2,m>1&&m==n}},0],GraphData[#,"HamiltonianCycleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

HamiltonianPathCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{(n!)^2,m==n},{Max[m,n]!Min[m,n]!/2,Abs[m-n]==1}},0],GraphData[#,"HamiltonianPathCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

HamiltonianNumber

{n,n}: 2 n

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2n,m ==n||Min[m,n]==1},{m n,Min[m,n]==2}},m+n+Abs[m-n]],GraphData[#,"HamiltonianNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

HamiltonianPathCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{n!^2,m==n},{Max[m,n]!Min[m,n]!/2,Abs[n-m]==1}},0],GraphData[#,"HamiltonianPathCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{n,n+1}},"HamiltonianPathCount"],{n,9}]

FindSequenceFunction[%,n]//FunctionExpand

Table[n!(n+1)!/2,{n,9}]

HamiltonianWalkCount

Table[n! (n-1)!/2,{n,10}]

{n,n}: Piecewise[{{1, n == 1}}, n! (n - 1)!/2]

Product[(k^2+3k+2),{k,n-1}]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1}},(((Max[m,n]-1)! Min[m,n]!)/(2 Abs[n-m]!))],GraphData[#,"HamiltonianWalkCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"HamiltonianWalkCount"],{n,2,10}]

FindSequenceFunction[DeleteCases[%,_Missing],n-1]

Table[GraphData[{"CompleteBipartite",{3,n}},"HamiltonianWalkCount"],{n,3,10}]

HararyIndex

{n,n}: n (3 n - 1)/2

(m(m-1)+(3+4(m-1))n+n^2)//Expand

Simplify[(1/4)((m^2)+(n^2)-(m+n))+m n/.m->n]

(1/4)((m^2)+(n^2)-(m+n))+m n

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(1/4)((m^2)+(n^2)-(m+n))+m n,GraphData[#,"HararyIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{1,n}},"HararyIndex"],{n,1,10}]

FindSequenceFunction[%,n]//Factor

Table[GraphData[{"CompleteBipartite",{2,n}},"HararyIndex"],{n,2,10}]

FindSequenceFunction[%,n-1]//Factor

Table[GraphData[{"CompleteBipartite",{3,n}},"HararyIndex"],{n,3,10}]

FindSequenceFunction[%,n-2]//Factor

Table[GraphData[{"CompleteBipartite",{4,n}},"HararyIndex"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

Table[GraphData[{"CompleteBipartite",{5,n}},"HararyIndex"],{n,5,10}]

FindSequenceFunction[%,n-4]//Factor

Sum[2k,{k,n}]

Table[n (1+n),{n,4}]

Table[3+4n,{n,4}]

Table[(1/4)(n(n+1)+(3+4n)m+m^2),{m,5},{n,5}]

FullSimplify[(1/4)(m(m+1)+(3+4m)n+n^2)]

HexagonCount

{n,n}: 6 Binomial[n,3]^2

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],6 Binomial[m,3]Binomial[n,3],GraphData[#,"HexagonCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

6 Binomial[m,3]Binomial[n,3]//FullSimplify

IdiosyncraticPolynomial

{n,n}: (x + y)^(-2 + 2 n) (x + y + n (1 - y)) (x + y - n (1 + y))

Expand[(x+y+n (1-y)) (x+y-n (1+y))]

FullSimplify[(x+y)^(m+n-2) (x^2+(2-m-n)x y+y^2(m-1)(n-1)-m n)/.m->n]

FullSimplify[(x+y)^(-2+2 n) (x+y+n (1-y)) (x+y-n (1+y))-(((x+y))^(-2+2 n)) (n+x+y-n y) (x+y-n (1+y))]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],FullSimplify@Expand[(x+y)^(m+n-2) (x^2+(2-m-n)x y+y^2(m-1)(n-1)-m n)/GraphData[#,"IdiosyncraticPolynomial"][x,y]]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

IncidenceMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"IncidenceMatrix"],{n,5}]

IndependenceNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Max[m,n],GraphData[#,"IndependenceNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

IndependencePolynomial

{n,n}: -1+2 (((1+x))^n)

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[(1+x)^m+(1+x)^n-1-GraphData[#,"IndependencePolynomial"][x]]}]&/@GraphData["CompleteBipartite"],{_,0}]

IndependenceRatio

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],((Max[m,n])/(m+n)),GraphData[#,"IndependenceRatio"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

IndependentEdgeSetCount

A086885

{n,n}: n! LaguerreL[n,-1]

m!LaguerreL[m,n-m,-1]/.m->n

Table[m!LaguerreL[m,n-m,-1],{n,10},{m,n}]

Table[GraphData[{"CompleteBipartite",{m,n}},"IndependentEdgeSetCount"],{n,10},{m,n}]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],m!LaguerreL[m,n-m,-1],GraphData[#,"IndependentEdgeSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

IndependentVertexSetCount

{n,n}: -1+(2^(1+n))

(2^m)+(2^n)-1/.m->n

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(2^m)+(2^n)-1,GraphData[#,"IndependentVertexSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"IndependentVertexSetCount"],{n,2,10}]

FindSequenceFunction[%,n-1]

Table[GraphData[{"CompleteBipartite",{3,n}},"IndependentVertexSetCount"],{n,3,10}]

FindSequenceFunction[%,n-2]

Table[GraphData[{"CompleteBipartite",{4,n}},"IndependentVertexSetCount"],{n,4,10}]

FindSequenceFunction[%,n-3]

Sum[2^k,{k,n}]

Table[(2^n)-1,{n,4}]

IntersectionNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],XXX,GraphData[#,"IntersectionNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

KirchhoffIndex

{n,n}: -3+4 n

FullSimplify[(((n^3)-(n^2)+m n(n-1)+(n-1) m^2+m^3)/(n m))]

FullSimplify[((((m^2)+(n^2))(m+n-1))/(m n))-1/.m->n]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],((((m^2)+(n^2))(m+n-1))/(m n))-1,GraphData[#,"KirchhoffIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"KirchhoffIndex"],{n,2,10}]

FindSequenceFunction[%,n-1]//Factor

Table[GraphData[{"CompleteBipartite",{3,n}},"KirchhoffIndex"],{n,3,10}]

FindSequenceFunction[%,n-2]//Factor

Table[GraphData[{"CompleteBipartite",{4,n}},"KirchhoffIndex"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

Table[GraphData[{"CompleteBipartite",{5,n}},"KirchhoffIndex"],{n,5,10}]

FindSequenceFunction[%,n-4]//Factor

Table[(n^3)-(n^2),{n,2,5}]

Table[n(n-1),{n,2,5}]

Table[(((n^3)-(n^2)+m n(n-1)+(n-1) m^2+m^3)/(n m)),{n,5},{m,n}]

Table[GraphData[{"CompleteBipartite",{m,n}},"KirchhoffIndex"],{n,5},{m,n}]

KirchhoffSumIndex

{n,n}: -2+3 n

Factor[(((m+n)(m(m-1)+(m-1)n+n^2))/(2n m))]

FullSimplify[(((m+n) ((m^2)+(n^2)+m n-(m+n)))/(2 m n))/.m->n]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(((m+n) ((m^2)+(n^2)+m n-(m+n)))/(2 m n)),GraphData[#,"KirchhoffSumIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"KirchhoffSumIndex"],{n,2,10}]

FindSequenceFunction[%,n-1]//Factor

Table[GraphData[{"CompleteBipartite",{3,n}},"KirchhoffSumIndex"],{n,3,10}]

FindSequenceFunction[%,n-2]//Factor

Table[GraphData[{"CompleteBipartite",{4,n}},"KirchhoffSumIndex"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

Table[GraphData[{"CompleteBipartite",{5,n}},"KirchhoffSumIndex"],{n,5,10}]

FindSequenceFunction[%,n-4]//Factor

Table[n(n-1),{n,2,5}]

Table[(((m+n)(m(m-1)+(m-1)n+n^2))/(2n m)),{n,5},{m,n}]

Table[GraphData[{"CompleteBipartite",{m,n}},"KirchhoffSumIndex"],{n,5},{m,n}]

LaplacianMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"LaplacianMatrix"],{n,5}]

MatrixForm/@Table[With[{z=ConstantArray[0,n {1,1}],o=ConstantArray[-1,n {1,1}]},ArrayFlatten[{{z,o},{o,z}}]]+n IdentityMatrix[2 n],{n,5}]

LaplacianPolynomial

{n,n}: (x-2n)(((x-n))^(2(n-1)))x

FullSimplify[(x-m-n)(((x-m))^(n-1))(((x-n))^(m-1))x/.m->n]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[(x-m-n)(((x-m))^(n-1))(((x-n))^(m-1))x/GraphData[#,"LaplacianPolynomial"][x]]}]&/@GraphData["CompleteBipartite"],{_,-1|1}]

LeafCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{Max[m,n],Min[m,n]==1}},0],GraphData[#,"LeafCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

LongestCycleCount

{n,n}: Piecewise[{{0,n==1}},n!(n-1)!/2

((m!(m-1)!n!)/(m!(n-m)!2))

(((Min[m,n]-1)! Max[m,n]!)/(2 Abs[n-m]!))/.m->n

(m-1)!m!Binomial[n,m]/2//FullSimplify

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]==1}},(((Min[m,n]-1)! Max[m,n]!)/(2 Abs[n-m]!))],GraphData[#,"LongestCycleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{0,m==1}},(m-1)!m!Binomial[n,m]/2],GraphData[#,"LongestCycleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"LongestCycleCount"],{n,2,10}]

FindSequenceFunction[%,n-1]

Table[GraphData[{"CompleteBipartite",{3,n}},"LongestCycleCount"],{n,3,10}]

FindSequenceFunction[%,n-2]//Factor

2!3!Binomial[n,3]/2

Table[GraphData[{"CompleteBipartite",{4,n}},"LongestCycleCount"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

3! 4!Binomial[n,4]/2

Table[GraphData[{"CompleteBipartite",{5,n}},"LongestCycleCount"],{n,5,10}]

FindSequenceFunction[%,n-4]//Factor

4!5!Binomial[n,5]/2

Table[GraphData[{"CompleteBipartite",{m,n}},"LongestCycleCount"],{n,5},{m,n}]

Table[Piecewise[{{0,m==1}},(m-1)!m!Binomial[n,m]/2],{n,5},{m,n}]

LovaszNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Max[m,n],GraphData[#,"LovaszNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

LucasCube

Entity["Graph",{"CompleteBipartite",{m,n}}]["LucasCube"]

GraphData[#,"NotationRules","CompleteBipartite"]&/@GraphData[{"CompleteBipartite","LucasCube"}]

MatchingGeneratingPolynomial

Factor[Table[(x^m)m!LaguerreL[m,n-m,-1/x],{n,5},{m,n}]]

Expand[Table[GraphData[{"CompleteBipartite",{m,n}},"MatchingGeneratingPolynomial"][x]-(x^m)m!LaguerreL[m,n-m,-1/x],{n,10},{m,n}]]

MatchingNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Min[m,n],GraphData[#,"MatchingNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MatchingPolynomial

Table[(((-1))^m)(x^(n-m))m!LaguerreL[m,n-m,(x^2)],{n,5},{m,n}]

Factor/@Table[(((-1))^m)(x^(n-m))m!LaguerreL[m,n-m,(x^2)],{m,5},{n,m}]

Table[GraphData[{"CompleteBipartite",{m,n}},"MatchingPolynomial"][x],{n,5},{m,n}]

Table[Expand[GraphData[{"CompleteBipartite",{m,n}},"MatchingPolynomial"][x]-(((-1))^m)(x^(n-m))m!LaguerreL[m,n-m,(x^2)]],{n,10},{m,n}]

MaximalCliqueCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],m n,GraphData[#,"MaximalCliqueCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MaximalIndependentEdgeSetCount

{n,n}: n!

Simplify[((n!)/((n-m)!))/.m->n]

Simplify[m!Binomial[n,m]/.m->n]

((m!n!)/(m!(n-m)!))

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],((Max[m,n]!)/(Abs[n-m]!)),GraphData[#,"MaximalIndependentEdgeSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],m!Binomial[n,m],GraphData[#,"MaximalIndependentEdgeSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"MaximalIndependentEdgeSetCount"],{n,2,10}]

FindSequenceFunction[%,n-1]//Simplify

Table[GraphData[{"CompleteBipartite",{3,n}},"MaximalIndependentEdgeSetCount"],{n,3,10}]

FindSequenceFunction[%,n-2]//Factor

3!Binomial[n,3]

MaximalIndependentVertexSetCount

{n,n}: 2

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],2,GraphData[#,"MaximalIndependentVertexSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MaximalIrredundantSetCount

Sort@Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"MaximalIrredundantSetCount"],Piecewise[{{2,Min[m,n]==1}},m n +2]}&/@GraphData["CompleteBipartite"]]

DeleteCases[%,{_,x_,x_}]

MaximumCliqueCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],m n,GraphData[#,"MaximumCliqueCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MaximumIndependentEdgeSetCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],((Max[m,n]!)/(Abs[n-m]!)),GraphData[#,"MaximumIndependentEdgeSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MaximumIndependentVertexSetCount

{n,n}: 2

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n}},1],GraphData[#,"MaximumIndependentVertexSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MaximumLeafNumber

GraphData[{"CompleteBipartite",{1,1}}]

GraphData[{"CompleteBipartite",{1,1}},"MaximumLeafNumber"]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{m+n-1,Min[m,n]==1}},m+n-2],GraphData[#,"MaximumLeafNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MaximumVertexDegree

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Max[m,n],GraphData[#,"MaximumVertexDegree"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MeanDistance

Expand[(m^2+(m+n) (n-1))]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],2 (m^2+n^2+m n-(m+n))/(m+n)^2,GraphData[#,"MeanDistance"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MinimalDominatingSetCount

Block[{m,n},Sort[{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"MinimalDominatingSetCount"],Piecewise[{{2,Min[m,n]==1}},m n+2]}&/@GraphData["CompleteBipartite"]]]

DeleteCases[%,{_,x_,x_}]

MinimalDominatingSetSignature

Block[{m,n},Sort[{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"MinimalDominatingSetSignature"],Piecewise[{{2,Min[m,n]==1}},m n+2]}&/@GraphData["CompleteBipartite"]]]//Column

MinimalEdgeCoverCount

ser=Series[Exp[x Exp[y]+y Exp[x]-x-y-x y]-1,{x,0,20},{y,0,20}];

Block[{m,n},Sort[{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"MinimalEdgeCoverCount"],m!n!Coefficient[ser,x^m y^n]}&/@GraphData["CompleteBipartite"]]]

DeleteCases[%,{_,x_,x_}]

MinimumCliqueCoveringCount

A019538

{n,n}: n!

Sum[(((-1))^(k+m))(k^n)Binomial[m,k],{k,n}]/.m->n

Table[%,{n,10}]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Min[m,n]!StirlingS2[Max[m,n],Min[m,n]],GraphData[#,"MinimumCliqueCoveringCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"MinimumCliqueCoveringCount"],{n,2,10}]

FindSequenceFunction[%,n-1]

Table[GraphData[{"CompleteBipartite",{3,n}},"MinimumCliqueCoveringCount"],{n,3,10}]

FindSequenceFunction[%,n-2]

Table[GraphData[{"CompleteBipartite",{4,n}},"MinimumCliqueCoveringCount"],{n,4,10}]

FindSequenceFunction[Most@%,n-4]

4^n-C(4,3)*3^n+C(4,2)*2^n-C(4,1)

Table[GraphData[{"CompleteBipartite",{m,n}},"MinimumCliqueCoveringCount"],{n,5},{m,n}]

Table[Sum[(((-1))^(k+m))(k^n)Binomial[m,k],{k,n}],{n,5},{m,n}]

Table[m!StirlingS2[n,m],{n,10},{m,n}]

Sum[(((-1))^(k+m))(k^n)Binomial[m,k],{k,n}]

MinimumConnectedDominatingSetCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{1,Min[m,n]==1}},m n],GraphData[#,"MinimumConnectedDominatingSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MinimumDistinguishingLabelingCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{1,Min[m,n]==1}},m n],GraphData[#,"MinimumDistinguishingLabelingCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MinimumDominatingSetCount

{n,n}: Piecewise[{{2, n == 1}, {6, n == 2}}, n^2]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{2,m==n==1},{6,m==n==2},{1,Min[m,n]==1},{m n+1,Min[m,n]==2}},m n],GraphData[#,"MinimumDominatingSetCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MinimumEdgeCoverCount

A019538

{n,n}: n!

Table[GraphData[{"CompleteBipartite",{m,n}},"MinimumEdgeCoverCount"],{n,5},{m,n}]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Min[m,n]!StirlingS2[Max[m,n],Min[m,n]],GraphData[#,"MinimumEdgeCoverCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MinimumVertexDegree

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Min[m,n],GraphData[#,"MinimumVertexDegree"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

MolecularTopologicalIndex

{n,n}: 4 (n^2) (-1+2 n)

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],4m n(m +n-1),GraphData[#,"MolecularTopologicalIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Nonhamiltonian

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{False,m>1&&m==n}},True],GraphData[#,"Nonhamiltonian"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

NormalizedLaplacianMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"NormalizedLaplacianMatrix"],{n,5}]

MatrixForm/@Table[With[{i=IdentityMatrix[n],c=ConstantArray[-1/n,{n,n}]},ArrayFlatten[{{i,c},{c,i}}]],{n,5}]

OddChordlessCycleCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],0,GraphData[#,"OddChordlessCycleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

PathCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],1/2 Sum[k! l! Binomial[m,k]Binomial[n,l],{k,2,m},{l,2,n}],GraphData[#,"PathCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{m,n}},"CycleCount"],{n,10},{m,n}]//Column

Table[GraphData[{"CompleteBipartite",{2,n}},"CycleCount"],{n,2,10}]

FindSequenceFunction[%,n-1]

Table[GraphData[{"CompleteBipartite",{3,n}},"CycleCount"],{n,3,10}]

FindSequenceFunction[%,n-2]//FullSimplify

Table[GraphData[{"CompleteBipartite",{4,n}},"CycleCount"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

PathPolynomial

Pell

Entity["Graph",{"CompleteBipartite",{m,n}}]["Pell"]

GraphData[#,"NotationRules","CompleteBipartite"]&/@GraphData[{"CompleteBipartite","Pell"}]

PentagonCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],0,GraphData[#,"PentagonCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Perfect

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],True,GraphData[#,"Perfect"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ProjectivePlaneCrossingNumber

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{0,Min[m,n]<3}},Missing["NotAvailable"]],GraphData[#,"ProjectivePlaneCrossingNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Radius

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{1,Min[m,n]==1}},2],GraphData[#,"Radius"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

RankPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"RankPolynomial"][x,y],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

RectilinearCrossingNumber

A030179 (conjectured)

https://en.wikipedia.org/wiki/Turán%27s_brick_factory_problem

If edges are required to be drawn as straight line segments, rather than arbitrary curves, then some graphs need more crossings. However, the upper bound established by Zarankiewicz for the crossing numbers of complete bipartite graphs can be achieved using only straight edges. Therefore, if the Zarankiewicz conjecture is correct, then the complete bipartite graphs have rectilinear crossing numbers equal to their crossing numbers

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"RectilinearCrossingNumber"],{n,20}]

ReliabilityPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"ReliabilityPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

ResistanceMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"ResistanceMatrix"],{n,6}]

SigmaPolynomial

(((x^n BellB[n,1/x]))^2),

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[Subtract@@{(x^(m+n)) BellB[m,1/x] BellB[n,1/x],GraphData[#,"SigmaPolynomial"][x]}]}]&/@GraphData["CompleteBipartite"],{_,0}]

Skewness

m n-2(m+n)+4

Sort@DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"Skewness"],Piecewise[{{0,Min[m,n]==1}},m n-2(m+n)+4]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

SpanningTreeCount

see A068087

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],m^(n-1)*n^(m-1),GraphData[#,"SpanningTreeCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

SquareCount

{n,n}: ((Binomial[n,2])^2)

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Binomial[m,2]Binomial[n,2],GraphData[#,"SquareCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

StabilityIndex

{n,n}: n^2+1

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{m n+1,m==n||Mod[m,2]==Mod[n,2]}},0],GraphData[#,"StabilityIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

TopologicalIndex

{n,n}:4^n(1-2n)

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(((-2))^(m+n))(1-m-n),GraphData[#,"TopologicalIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

ToroidalCrossingNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ToroidalCrossingNumber"],{n,20}]

Traceable

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{True,Abs[n-m]<2}},False],GraphData[#,"Traceable"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

TriangleCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],0,GraphData[#,"TriangleCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

TuttePolynomial

An e.g.f. is known

Untraceable

Table[GraphData[{"CompleteBipartite",{n,n}},"Untraceable"],{n,20}]

VertexConnectivity

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Min[m,n],GraphData[#,"VertexConnectivity"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

VertexCount

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],m+n,GraphData[#,"VertexCount"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

VertexCoverNumber

{n,n}: n

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Min[m,n],GraphData[#,"VertexCoverNumber"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

VertexCoverPolynomial

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Expand[(#^m (#+1)^n+#^n (#+1)^m-#^(m+n)&)[x]-GraphData[#,"VertexCoverPolynomial"][x]]}]&/@GraphData["CompleteBipartite"],{_,0}]

VertexDegrees

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Join[ConstantArray[n,m],ConstantArray[m,n]],GraphData[#,"VertexDegrees"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

VertexTransitive

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],Piecewise[{{True,m==n}},False],GraphData[#,"VertexTransitive"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

WienerIndex

{n,n}:n (-2+3 n)

(m^2)+(n^2)+m n-(m+n)/.m->n

Table[GraphData[{"CompleteBipartite",{m,n}},"WienerIndex"],{n,5},{m,n}]

Expand[n(n-1)+(n-1)m+m^2]

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],(m^2)+(n^2)+m n-(m+n),GraphData[#,"WienerIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"WienerIndex"],{n,2,10}]

FindSequenceFunction[%,n-1]//Factor

Table[GraphData[{"CompleteBipartite",{3,n}},"WienerIndex"],{n,3,10}]

FindSequenceFunction[%,n-2]//Factor

Table[GraphData[{"CompleteBipartite",{4,n}},"WienerIndex"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

Table[GraphData[{"CompleteBipartite",{5,n}},"WienerIndex"],{n,5,10}]

FindSequenceFunction[%,n-4]//Factor

Table[n(n-1)+(n-1)m+m^2,{n,5},{m,n}]

WienerSumIndex

{n,n}: (((n^2) (1-3 n+3 (n^2)))/(-1+2 n))

Simplify[((m n ((m^2)+(n^2)+4 m n-3 (m+n)+2))/(2 (m+n-1)))/.m->n]

Table[GraphData[{"CompleteBipartite",{m,n}},"WienerSumIndex"],{n,5},{m,n}]

Expand[((m n((n-1)(n-2)+(4n-3)m+(m^2)))/(2(m+n-1)))]//Factor

DeleteCases[Block[{m,n},{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],((m n ((m^2)+(n^2)+4 m n-3 (m+n)+2))/(2 (m+n-1))),GraphData[#,"WienerSumIndex"]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

Table[GraphData[{"CompleteBipartite",{2,n}},"WienerSumIndex"],{n,2,10}]

FindSequenceFunction[%,n-1]//Factor

Table[GraphData[{"CompleteBipartite",{3,n}},"WienerSumIndex"],{n,3,10}]

FindSequenceFunction[%,n-2]//Factor

Table[GraphData[{"CompleteBipartite",{4,n}},"WienerSumIndex"],{n,4,10}]

FindSequenceFunction[%,n-3]//Factor

Table[GraphData[{"CompleteBipartite",{5,n}},"WienerSumIndex"],{n,5,10}]

FindSequenceFunction[%,n-4]//Factor

Table[(n-1)(n-2),{n,5}]

Table[4n-3,{n,5}]

Table[((m n((n-1)(n-2)+(4n-3)m+(m^2)))/(2(m+n-1))),{n,5},{m,n}]

Table[GraphData[{"CompleteBipartite",{m,n}},"WienerSumIndex"],{n,5},{m,n}]

Properties n×(n-1)

HamiltonianPathCount

A010796

Table[GraphData[{"CompleteBipartite",{n,n+1}},"HamiltonianPathCount"],{n,19}]

FindSequenceFunction[DeleteMissing@seq,n]//FunctionExpand//FullSimplify

Table[(n-1)!n!/2,{n,2,20}]

Properties n×n

Acyclic

Table[GraphData[{"CompleteBipartite",{n,n}},"Acyclic"],{n,20}]

AdjacencyMatrixCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"AdjacencyMatrixCount"],{n,20}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//FunctionExpand//FullSimplify

Table[Multinomial[n,n]/2,{n,20}]

Table[Binomial[2n,n]/2,{n,20}]

Table[(2n)!/(((n!))^2)/2,{n,20}]

FunctionExpand[Multinomial[n,n]/2]

gf=x FindGeneratingFunction[seq,x]

SeriesCoefficient[gf,{x,0,n}]//FullSimplify

Arboricity

Table[GraphData[{"CompleteBipartite",{n,n}},"Arboricity"],{n,20}]

Table[Floor[n/2]+1,{n,20}]

ArcTransitive

Table[GraphData[{"CompleteBipartite",{n,n}},"ArcTransitive"],{n,20}]

ArcTransitivity

Table[GraphData[{"CompleteBipartite",{n,n}},"ArcTransitivity"],{n,20}]

AutomorphismCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"AutomorphismCount"],{n,20}]

FindSequenceFunction[seq,n]

FunctionExpand[%]

BalabanIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"BalabanIndex"],{n,20}]

FindSequenceFunction[seq,n]//Factor

Bandwidth

A001651

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Bandwidth"],{n,20}]

FindSequenceFunction[seq,n]//FullSimplify

Table[Floor[(3 n-1)/2],{n,20}]

Floor[(3 Range[70]-1)/2]

FullSimplify[Floor[(Max[m,n]-1)/2]+Min[m,n],m==n]

Table[n+Floor[(1/2) (-1+n)],{n,20}]

BridgeCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"BridgeCount"],{n,20}]

BurningNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"BurningNumber"],{n,20}]

Do[Print[{n,BurningNumber[System`CompleteGraph[{n,n}]]//Timing}],{n,20}]

CharacteristicPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"CharacteristicPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(x^(-2+2 n)) (-n+x) (n+x),{n,20}]

FullSimplify[poly2-poly]

ChordCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ChordCount"],{n,20}]

Table[GraphData[{"CompleteBipartite",{n,n}},"EdgeCount"],{n,10}]

Do[Print[{n,Length[Chords[System`CompleteGraph[{n,n}]]]//Timing}],{n,7}]

ChordlessCycleCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ChordlessCycleCount"],{n,20}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]//Factor

Binomial[n,2]^2

ChromaticInvariant

A048144

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ChromaticInvariant"],{n,20}]

FindLinearRecurrence[seq]

FindSequenceFunction[Drop[seq,2],n]

gf=x FindGeneratingFunction[seq,x]

Sum[(((-1))^(n-j))Binomial[n,j](((Exp[j x]-1))^n),{j,0,n}]

Series[Sum[(((-1))^(n-j))Binomial[n,j](((Exp[j x]-1))^n),{n,1,5},{j,0,n}],{x,0,10}]

Table[Sum[(k!)^2*StirlingS2[n,k]^2,{k,0,n}]/n!,{n,20}]

Sum[(k!)^2*StirlingS2[n-1,k]^2,{k,0,n-1}]

Table[%,{n,20}]

Sum[StirlingS2[n,k](((x-k))^n)FactorialPower[x,k],{k,n}]

Table[Sum[StirlingS2[n,k](((x-k))^n)FactorialPower[x,k],{k,n}],{n,10}]//FunctionExpand//Factor

Sum[StirlingS2[n,k](((x-k))^n)((Gamma[1+x])/(Gamma[1-k+x])),{k,n}]

D[((Gamma[1+x])/(Gamma[1-k+x])),x]

Table[((Gamma[1+x])/(Gamma[1-k+x])),{k,4}]//FunctionExpand

Table[FactorialPower[x,k],{k,4}]//FunctionExpand

D[(((x-k))^n)FactorialPower[x,k],x]//Simplify

FullSimplify[PolyGamma[0,1+x]-PolyGamma[0,1-k+x]]

((((-k+x))^(n-1))  +(((-k+x))^n) (HarmonicNumber[x]-HarmonicNumber[-k+x]))FactorialPower[x,k]

Limit[%,x->1]

Table[FactorialPower[1,k] ((((1-k))^(-1+n))+(((1-k))^n) (1-HarmonicNumber[1-k])),{k,4}]

FactorialPower[1,10]

D[(((x-k))^n)(((-1))^n)Pochhammer[-x,n],x]//FullSimplify

Limit[ (((-k+x))^(-1+n)) Pochhammer[-x,n] (n+(k-x) (PolyGamma[0,n-x]-PolyGamma[0,-x])),x->1]

Limit[Table[Sum[StirlingS2[n,k](((-1))^n) (((-k+x))^(-1+n)) Pochhammer[-x,n] (n+(k-x) (PolyGamma[0,n-x]-PolyGamma[0,-x])),{k,n}],{n,10}],x->1]

Table[Sum[StirlingS2[n,k](((k-1))^n) Gamma[n-1],{k,n}],{n,10}]

ChromaticNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ChromaticNumber"],{n,20}]

ChromaticPolynomial

Entity["Graph",{"CompleteBipartite",{n,n}}]["ChromaticPolynomial"]

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"ChromaticPolynomial"][x],{n,k0=1,20}])//Column

Take[poly,5]//Expand//Column

Cf. A182553

Sum[StirlingS2[n,k](((x-k))^n)((Gamma[1+x])/(Gamma[1-k+x])),{k,n}]

poly2=Factor/@Table[FunctionExpand@Sum[StirlingS2[n,k](((x-k))^n)((Gamma[1+x])/(Gamma[1-k+x])),{k,n}],{n,20}]

FullSimplify[poly2-poly]

poly3=Factor/@Table[FunctionExpand@Sum[StirlingS2[n,k](((x-k))^n)FactorialPower[x,k],{k,n}],{n,20}]

FullSimplify[poly3-poly]

Circumference

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Circumference"],{n,20}]

FindSequenceFunction[Drop[seq,2],n]

Classes

GraphData[{"CompleteBipartite",{1,1}},"#"]

Intersection@@(GraphData[#,"Classes"]&/@(Cases[("CompleteBipartite"/.GraphData[#,"NotationRules"])&/@GraphData["CompleteBipartite"],{n_,n_}:>{"CompleteBipartite",{n,n}}]))

CliqueCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CliqueCount"],{n,20}]

FindSequenceFunction[seq,n]//Factor

CliqueCoveringNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CliqueCoveringNumber"],{n,20}]

FindSequenceFunction[seq,n]

CliqueNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CliqueNumber"],{n,20}]

CliquePolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"CliquePolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(((1+n x))^2),{n,20}]

FullSimplify[poly2-poly]

ComplementOddChordlessCycleCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ComplementOddChordlessCycleCount"],{n,20}]

ConnectedComponentCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ConnectedComponentCount"],{n,20}]

ConnectedDominatingSetCount

A060867

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ConnectedDominatingSetCount"],{n,20}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

FindSequenceFunction[DeleteCases[Rest@seq,_Missing],n-1]

Table[Piecewise[{{3,n==1}},((((2^n)-1))^2)],{n,5}]

GraphData[{"CompleteBipartite",{1,1}},"LabeledGraph"]

ConnectedDominationNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ConnectedDominationNumber"],{n,20}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedDominationPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"ConnectedDominationPolynomial"],{n,k0=2,20}]/.f_Function:>f[x])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

A286191

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ConnectedInducedSubgraphCount"],{n,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{8,-21,22,-8},{3,13,55,233},20]

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

Table[((((2^n)-1))^2)+2n,{n,20}]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Series[gf,{x,0,20}]

Refine[SeriesCoefficient[gf,{x,0,n}],n>0]

CoefficientList[Series[((3-11 x+14 (x^2))/((((-1+x))^2) (1-6 x+8 (x^2)))),{x,0,20}],x]

ConnectedInducedSubgraphPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"ConnectedInducedSubgraphPolynomial"][x],{n,k0=2,10}],_Missing[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

CrossingNumber

A030179 (conjectured)

Conjectured to be crossing number of complete bipartite graph K_{n,n}.

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CrossingNumber"],{n,20}]

Table[((Floor[(n-1)^2/4])^2),{n,20}]

((Floor[Range[0,30]^2/4])^2)

CycleCount

A070968

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CycleCount"],{n,20}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

1/2 Sum[\[FormalK]! (\[FormalK]-1)! Binomial[n,\[FormalK]]^2,{\[FormalK],2,n}]

Table[1/2 Sum[\[FormalK]! (\[FormalK]-1)! Binomial[n,\[FormalK]]^2,{\[FormalK],2,n}],{n,20}]

RSolve[(n-2)^2*(2*n^3-19*n^2+58*n-59)*a[n]==2*(2*n^7-31*n^6+200*n^5-700*n^4+1442*n^3-1764*n^2+1205*n-363)*a[n-1]-(n-1)^2*(2*n^7-35*n^6+266*n^5-1139*n^4+2962*n^3-4671*n^2+4130*n-1578)*a[n-2]+2*(n-2)^2*(n-1)^2*(2*n^5-26*n^4+134*n^3-342*n^2+431*n-217)*a[n-3]-(n-3)^2*(n-2)^2*(n-1)^2*(2*n^3-13*n^2+26*n-18)*a[n-4],a[n],n]

CyclePolynomial

A291909

(poly=DeleteMissing@Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"CyclePolynomial"],{n,k0=1,20}]/.f_Function:>f[x])//Column

Length/@poly

CoefficientList[Take[poly,5],x]//Column

coef=Factor/@FindLinearRecurrence[poly]

(1/2)Sum[((Binomial[n,k])^2)k!(k-1)!(x^(2k)),{k,2,n}]

Table[(1/2)Sum[((Binomial[n,k])^2)k!(k-1)!(x^(2k)),{k,2,n}],{n,5}]//Factor

Take[poly,5]

CoefficientList[Table[Sum[((Binomial[n,k])^2)k!(k-1)!(x^k),{k,2,n}]/2,{n,10}],x]//Flatten

Table[(1/2)Sum[((Binomial[n,k])^2)k!(k-1)!(x^(2k)),{k,2,n}],{n,5}]//Expand//Column

Cyclic

Table[GraphData[{"CompleteBipartite",{n,n}},"Cyclic"],{n,20}]

CyclomaticNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CyclomaticNumber"],{n,20}]

FindSequenceFunction[seq,n]

DetourIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"DetourIndex"],{n,20}]

FindSequenceFunction[seq,n]//Factor

DetourMatrix

GraphData[{"CompleteBipartite",{2,2}},"#"]

MatrixForm/@(d1=Table[GraphData[{"CompleteBipartite",{n,n}},"DetourMatrix"],{n,5}])

MatrixForm/@(d2=Table[SparseArray[{{i_,i_}->0,{i_,j_}/;((i≤n&&j≤n)||(i>n&&j>n))->2 n-2},2 n,2 n-1],{n,5}])

d1-d2

DetourPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"DetourPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[((2 n-2+#)^(2 n-2) (3 n-2+#) (#-(2-5 n+4 n^2))&)[x],{n,20}]

FullSimplify[poly2-poly]

Diameter

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Diameter"],{n,20}]

DistanceMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"DistanceMatrix"],{n,5}]

MatrixForm/@Table[With[{z=ConstantArray[2,n {1,1}],o=ConstantArray[1,n {1,1}]},ArrayFlatten[{{z,o},{o,z}}]]-2 IdentityMatrix[2 n],{n,5}]

DistancePolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"DistancePolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(((2+x))^(-2+2 n)) (2-3 n+x) (2-n+x),{n,20}]

FullSimplify[poly2-poly]

DistinguishingNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"DistinguishingNumber"],{n,20}]

DomaticNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"DomaticNumber"],{n,20}]

DominatingSetCount

A191341

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"DominatingSetCount"],{n,20}]

FindSequenceFunction[seq,n]//FullSimplify

seq=Table[3-(2^(1+n))+(4^n),{n,40}]

FindLinearRecurrence[seq]

LinearRecurrence[{7,-14,8},{3,11,51},20]

gf=x FindGeneratingFunction[seq,x]//Factor

CoefficientList[Series[-(((3-10 x+16 (x^2)))/((-1+x) (-1+2 x) (-1+4 x))),{x,0,20}],x]

DominationNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"DominationNumber"],{n,20}]

DominationPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"DominationPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

EdgeChromaticNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"EdgeChromaticNumber"],{n,20}]

EdgeConnectivity

Table[GraphData[{"CompleteBipartite",{n,n}},"EdgeConnectivity"],{n,20}]

EdgeCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"M"],{n,20}]

FindSequenceFunction[seq,n]

EdgeCoverCount

A048291

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"EdgeCoverCount"],{n,20}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

Sum[(((-1))^k)Binomial[n,k](2^((n-k)n))(((1-(2^(k-n))))^n),{k,0,n}]

Table[Sum[(((-1))^k)Binomial[n,k](2^((n-k)n))(((1-(2^(k-n))))^n),{k,0,n}] ,{n,20}]

Table[(Sum[(-1)^\[FormalK] Binomial[n,\[FormalK]] ((#+1)^(n-\[FormalK])-1)^n,{\[FormalK],0,n}]&)[1],{n,20}]

EdgeCoverNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"EdgeCoverNumber"],{n,20}]

EdgeCoverPolynomial

A055599

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"EdgeCoverPolynomial"][x],{n,k0=1,10}])//Column

Take[poly,5]//Expand

CoefficientList[#,x]&/@%

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

EulerianCycleCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"EulerianCycleCount"],{n,20}]

seq[[2;;All;;2]]

FaceCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"FaceCount"],{n,20}]

FibonacciCube

Entity["Graph",{"CompleteBipartite",{n,n}}]["FibonacciCube"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"FibonacciCube"],{n,20}]

FlowPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"FlowPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

FractionalChromaticNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"FractionalChromaticNumber"],{n,20}]

FractionalEdgeChromaticNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"FractionalEdgeChromaticNumber"],{n,20}]

Girth

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Girth"],{n,20}]

Gonality

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Gonality"],{n,20}]

HamiltonConnected

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HamiltonConnected"],{n,20}]

HamiltonDecompositionCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HamiltonDecompositionCount"],{n,20}]

Hamiltonian

Table[GraphData[{"CompleteBipartite",{n,n}},"Hamiltonian"],{n,20}]

HamiltonianCycleCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HamiltonianCycleCount"],{n,20}]

FindSequenceFunction[Rest@seq,n-1]//FullSimplify

Table[n! (n-1)!/2,{n,20}]

HamiltonianNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HamiltonianNumber"],{n,20}]

FindSequenceFunction[seq,n]

HamiltonianPathCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HamiltonianPathCount"],{n,20}]

FindSequenceFunction[Rest@seq,n]//FullSimplify

Table[(n!)^2,{n,20}]

HamiltonianWalkCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HamiltonianWalkCount"],{n,20}]

Table[Piecewise[{{1,n==1}},n!(n-1)!/2],{n,20}]

HararyIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HararyIndex"],{n,20}]

FindSequenceFunction[seq,n]

HexagonCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HexagonCount"],{n,20}]

FindSequenceFunction[seq,n]//Factor

6 Binomial[n,3]^2

IdiosyncraticPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"IdiosyncraticPolynomial"][x,y],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

IncidenceMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"IncidenceMatrix"],{n,5}]

IndependenceNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"IndependenceNumber"],{n,20}]

IndependencePolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"IndependencePolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

IndependenceRatio

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"IndependenceRatio"],{n,20}]

IndependentEdgeSetCount

A002720

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"IndependentEdgeSetCount"],{n,20}]

(x^3)FindGeneratingFunction[seq,x]

FindSequenceFunction[seq,n]

Table[Sum[k!((Binomial[n,k])^2),{k,0,n}],{n,20}]

Sum[k!((Binomial[n,k])^2),{k,0,n}]

Table[(((-1))^n) HypergeometricU[-n,1,-1],{n,20}]

Table[n! LaguerreL[n,-1],{n,20}]

IndependentVertexSetCount

A000225

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"IndependentVertexSetCount"],{n,20}]

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

seq=LinearRecurrence[{3,-2},{1,3},20]

FindGeneratingFunction[seq,x]

CoefficientList[Series[(1/(1-3 x+2 (x^2))),{x,0,20}],x]

IntersectionNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"IntersectionNumber"],{n,20}]

IrredundantSetCount

A290707(n) for n > 1

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"IrredundantSetCount"],{n,20}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Series[((x (3-4 x-4 (x^2)+5 (x^3)-2 (x^4)))/((((-1+x))^3) (-1+2 x))),{x,0,20}]

SeriesCoefficient[gf,{x,0,n}]

FullSimplify[%,n==1]

seq=Table[-1+(2^(1+n))+(n^2),{n,0,40}]

FindLinearRecurrence[seq]

LinearRecurrence[{5,-9,7,-2},{4,11,24,47},{0,20}]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((1-x-2 (x^3))/((((-1+x))^3) (-1+2 x))),{x,0,20}],x]

KirchhoffIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"KirchhoffIndex"],{n,20}]

FindSequenceFunction[seq,n]

KirchhoffSumIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"KirchhoffSumIndex"],{n,20}]

FindSequenceFunction[seq,n]

LaplacianMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"LaplacianMatrix"],{n,5}]

MatrixForm/@Table[With[{z=ConstantArray[0,n {1,1}],o=ConstantArray[-1,n {1,1}]},ArrayFlatten[{{z,o},{o,z}}]]+n IdentityMatrix[2 n],{n,5}]

LaplacianPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"LaplacianPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(x-2n)(((x-n))^(2(n-1)))x,{n,20}]

FullSimplify[poly2-poly]

LeafCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"LeafCount"],{n,20}]

LongestCycleCount

A010796

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"LongestCycleCount"],{n,20}]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]//FunctionExpand

FindLinearRecurrence[seq]

gf=x FindGeneratingFunction[seq,x]

Table[Piecewise[{{0,n==1}},n!(n-1)!/2],{n,20}]

LovaszNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"LovaszNumber"],{n,20}]

LucasCube

Entity["Graph",{"CompleteBipartite",{n,n}}]["LucasCube"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"LucasCube"],{n,20}]

MatchingGeneratingPolynomial

A144084

Sum[(x^k)((Binomial[n,k])^2)k!,{k,0,n}]

FullSimplify[%]

FullSimplify[(((-x))^n) HypergeometricU[-n,1,-(1/x)]-n! x^n LaguerreL[n,-1/x],n∈Integers&&n>0]

Table[(((-x))^n) HypergeometricU[-n,1,-(1/x)],{n,5}]//Expand

Table[n! x^n LaguerreL[n,-1/x],{n,5}]//Expand

CoefficientList[Table[n! x^n LaguerreL[n,-1/x],{n,0,8}],x]//Flatten

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"MatchingGeneratingPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,0,10}]

FullSimplify[poly2-poly]

MatchingNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MatchingNumber"],{n,20}]

MatchingPolynomial

Not in OEIS

k-matchings:

((Binomial[n,k])^2)k!

Sum[(-1)^k (x^(2n-2k))((Binomial[n,k])^2)k!,{k,0,n}]

FullSimplify[%]

Table[HypergeometricU[-n,1,(x^2)],{n,5}]

Table[(((-1))^n) n! LaguerreL[n,(x^2)],{n,5}]

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"MatchingPolynomial"][x],{n,k0=1,10}])//Column

CoefficientList[poly,x]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,0,10}]

FullSimplify[poly2-poly]

MaximalCliqueCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximalCliqueCount"],{n,20}]

FindSequenceFunction[seq,n]//FunctionExpand

MaximalIndependentEdgeSetCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximalIndependentEdgeSetCount"],{n,20}]

FindSequenceFunction[seq,n]

MaximalIndependentVertexSetCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximalIndependentVertexSetCount"],{n,20}]

MaximalIrredundantSetCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximalIrredundantSetCount"],{n,20}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

SeriesCoefficient[gf,{x,0,n}]

MaximumCliqueCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximumCliqueCount"],{n,20}]

FindSequenceFunction[seq,n]

MaximumIndependentEdgeSetCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximumIndependentEdgeSetCount"],{n,20}]

FindSequenceFunction[seq,n]

MaximumIndependentVertexSetCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximumIndependentVertexSetCount"],{n,20}]

MaximumLeafNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximumLeafNumber"],{n,20}]

Table[Piecewise[{{2,n==1}},2n-2],{n,20}]

MaximumVertexDegree

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximumVertexDegree"],{n,20}]

MeanDistance

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MeanDistance"],{n,20}]

FindSequenceFunction[seq,n]

MinimalDominatingSetCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimalDominatingSetCount"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]//Factor

Series[gf,{x,0,20}]

SeriesCoefficient[gf,{x,0,n}]

Table[Piecewise[{{2,n==1}},n^2+2],{n,20}]

MinimalDominatingSetSignature

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimalDominatingSetSignature"],{n,20}]//Column

MinimalEdgeCoverCount

A210655

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimalEdgeCoverCount"],{n,20}]

T[p_,q_]:=T[p,q]=If[p==1||q===1,1,Sum[Binomial[q,r]*T[p-1,q-r],{r,2,q-1}]+q*Sum[Binomial[p-1,s]*T[p-s-1,q-1],{s,0,p-2}]];a[n_]:=T[n,n];Table[a[n],{n,1,20}]

With[{ser=Series[Exp[x Exp[y]+y Exp[x]-x-y-x y]-1,{x,0,20},{y,0,20}]},Table[(((n!))^2)Coefficient[ser,x^n y^n],{n,20}]]

SeriesCoefficient[Exp[x Exp[y]+y Exp[x]-x-y-x y]-1,{x,0,n},{y,0,n}]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]//Factor

Series[gf,{x,0,20}]

SeriesCoefficient[gf,{x,0,n}]

Table[Piecewise[{{2,n==1}},n^2+2],{n,20}]

MinimumCliqueCoveringCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimumCliqueCoveringCount"],{n,20}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

MinimumConnectedDominatingSetCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimumConnectedDominatingSetCount"],{n,20}]

FindSequenceFunction[DeleteCases[Rest@seq,_Missing],n-1]//FullSimplify

MinimumDistinguishingLabelingCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimumDistinguishingLabelingCount"],{n,20}]

MinimumDominatingSetCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimumDominatingSetCount"],{n,20}]

FindSequenceFunction[Rest[seq],n-1]

gf=x FindGeneratingFunction[seq,x]

SeriesCoefficient[gf,{x,0,n}]

MinimumEdgeCoverCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimumEdgeCoverCount"],{n,20}]

Table[n!,{n,20}]

MinimumVertexDegree

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MinimumVertexDegree"],{n,20}]

MolecularTopologicalIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MolecularTopologicalIndex"],{n,20}]

FindSequenceFunction[seq,n]//Factor

Nonhamiltonian

Table[GraphData[{"CompleteBipartite",{n,n}},"Nonhamiltonian"],{n,20}]

NormalizedLaplacianMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"NormalizedLaplacianMatrix"],{n,5}]

MatrixForm/@Table[With[{i=IdentityMatrix[n],c=ConstantArray[-1/n,{n,n}]},ArrayFlatten[{{i,c},{c,i}}]],{n,5}]

OddChordlessCycleCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"OddChordlessCycleCount"],{n,20}]

PathCount

A288035

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"PathCount"],{n,20}]

Table[Sum[((((n!))^2)/((n-Ceiling[k/2])!(n-Floor[k/2])!)),{k,2,2n}],{n,30}]

Sum[((((n!))^2)/((n-Ceiling[k/2])!(n-Floor[k/2])!)),{k,2,2n}]

FullSimplify[((((n!))^2)/((n-Ceiling[k/2])!(n-Floor[k/2])!)),Mod[k,2]==#]&/@{0,1}

Table[Sum[Piecewise[{{((((n!))^2)/((((-(k/2)+n)!))^2)),Mod[k,2]==0},{((((n!))^2)/((n-((k+1)/2))! (n-((k-1)/2))!)),Mod[k,2]==1}}],{k,2,2n}],{n,20}]

Sum[((((n!))^2)/((((n-k)!))^2)),{k,n}]//FullSimplify

Sum[((((n!))^2)/((n-k)! (n-k-1)!)),{k,n}]//FullSimplify

Table[BesselI[0,2] (((n!))^2)-HypergeometricPFQ[{1},{1+n,1+n},1]+BesselI[1,2] ((Gamma[1+n])^2)-n HypergeometricPFQ[{1},{n,1+n},1],{n,20}]//Round

FullSimplify[BesselI[0,2] (((n!))^2)-HypergeometricPFQ[{1},{1+n,1+n},1]+BesselI[1,2] ((Gamma[1+n])^2)-n HypergeometricPFQ[{1},{n,1+n},1]]

Gamma[n+1]-Factorial[n]//FullSimplify

Table[((n!)^2) (BesselI[0,2]+BesselI[1,2]-HypergeometricPFQRegularized[{1},{1+n,1+n},1])-n HypergeometricPFQ[{1},{n,1+n},1],{n,20}]//FunctionExpand

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>0]

PathPolynomial

(poly=Expand[Table[GraphData[{"CompleteBipartite",{n,n}},"PathPolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x]])//Column

poly=Table[Sum[((((n!))^2)/((n-Ceiling[k/2])!(n-Floor[k/2])!))(x^k),{k,2,2n}],{n,20}]

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

Table[Sum[((((n!))^2)/((((n-k)!))^2))(x^(2k)),{k,n}]+Sum[((((n!))^2)/((n-k)! (n-k-1)!))(x^(2k+1)),{k,n}],{n,4}]

Sum[((((n!))^2)/((((n-k)!))^2))(x^(2k)),{k,n}]//FullSimplify

Sum[((((n!))^2)/((n-k)! (n-k-1)!))(x^(2k+1)),{k,n}]//FullSimplify

FullSimplify[(x^(2 n)) (((n!))^2) Hypergeometric0F1Regularized[1,(1/(x^2))]-HypergeometricPFQ[{1},{1+n,1+n},(1/(x^2))]+(x^(2 n)) BesselI[1,(2/x)] ((Gamma[1+n])^2)-n x HypergeometricPFQ[{1},{n,1+n},(1/(x^2))]]

Table[(x^(2 n)) ((n!)^2) (BesselI[1,(2/x)]+Hypergeometric0F1Regularized[1,(1/(x^2))])-n x HypergeometricPFQ[{1},{n,1+n},(1/(x^2))]-HypergeometricPFQ[{1},{1+n,1+n},(1/(x^2))],{n,5}]//FunctionExpand

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

Pell

Entity["Graph",{"CompleteBipartite",{n,n}}]["Pell"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Pell"],{n,20}]

PentagonCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"PentagonCount"],{n,20}]

Perfect

Table[GraphData[{"CompleteBipartite",{n,n}},"Perfect"],{n,20}]

ProjectivePlaneCrossingNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ProjectivePlaneCrossingNumber"],{n,20}]

Radius

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Radius"],{n,20}]

RankPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"RankPolynomial"][x,y],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

RectilinearCrossingNumber

A030179 (conjectured)

https://en.wikipedia.org/wiki/Turán%27s_brick_factory_problem

If edges are required to be drawn as straight line segments, rather than arbitrary curves, then some graphs need more crossings. However, the upper bound established by Zarankiewicz for the crossing numbers of complete bipartite graphs can be achieved using only straight edges. Therefore, if the Zarankiewicz conjecture is correct, then the complete bipartite graphs have rectilinear crossing numbers equal to their crossing numbers

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"RectilinearCrossingNumber"],{n,20}]

ReliabilityPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"ReliabilityPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

ResistanceMatrix

MatrixForm/@Table[GraphData[{"CompleteBipartite",{n,n}},"ResistanceMatrix"],{n,6}]

SigmaPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"SigmaPolynomial"][x],{n,k0=1,10}])//Column

poly2=Table[(((x^n BellB[n,1/x]))^2),{n,20}]

FullSimplify[poly2-poly]

Skewness

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Skewness"],{n,20}]

FindSequenceFunction[Drop[seq,1],n-1]

Table[Piecewise[{{0,n==1}},(n-2)^2],{n,20}]

SpanningTreeCount

A068087

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"SpanningTreeCount"],{n,20}]

FindSequenceFunction[seq,n]

Table[n^(2 n-2),{n,20}]

SquareCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"SquareCount"],{n,20}]

FindSequenceFunction[seq,n]//Factor

((Binomial[n,2])^2)

StabilityIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"StabilityIndex"],{n,20}]

FindSequenceFunction[seq,n]

TopologicalIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"TopologicalIndex"],{n,20}]

FindSequenceFunction[seq,n]

ToroidalCrossingNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"ToroidalCrossingNumber"],{n,20}]

Traceable

Table[GraphData[{"CompleteBipartite",{n,n}},"Traceable"],{n,20}]

TriangleCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"TriangleCount"],{n,20}]

TuttePolynomial

An e.g.f. is known

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"TuttePolynomial"][x,y],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

Untraceable

Table[GraphData[{"CompleteBipartite",{n,n}},"Untraceable"],{n,20}]

VertexConnectivity

Table[GraphData[{"CompleteBipartite",{n,n}},"VertexConnectivity"],{n,20}]

VertexCount

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"VertexCount"],{n,20}]

FindSequenceFunction[seq,n]

VertexCoverNumber

Related to but not the same as IndependenceNumber

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"VertexCoverNumber"],{n,20}]

VertexCoverPolynomial

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"VertexCoverPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

VertexDegrees

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"VertexDegrees"],{n,20}]

VertexTransitive

Table[GraphData[{"CompleteBipartite",{n,n}},"VertexTransitive"],{n,20}]

WienerIndex

A000567

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"WienerIndex"],{n,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{3,-3,1},{1,8,21},{0,20}]

FindSequenceFunction[seq,n]//Factor

PolygonalNumber[8, Range[0,20]]

WienerSumIndex

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"WienerSumIndex"],{n,20}]

FindSequenceFunction[seq,n]//Factor

Graceful labelings

(Subscript[K, 5,5]) (1 fundamental labeling)

GraphData[{"CompleteBipartite",{4,4}},"GracefulLabelingCount"]

((GraphData[{"CompleteBipartite",{4,4}},"GracefulLabelingCount"])/(2GraphData[{"CompleteBipartite",{4,4}},"AutomorphismCount"]))

GraphData[{"CompleteBipartite",{4,4}},"GracefulLabelings"]

solution #1
  0  1  2  3  4
  5 10 15 20 25

A337793(5) = 57600
        0.00 real         0.00 user         0.00 sys

(Subscript[K, 6,6]) (7 fundamental labelings)

GraphData[{"CompleteBipartite",{6,6}},"GracefulLabelingCount"]

((GraphData[{"CompleteBipartite",{6,6}},"GracefulLabelingCount"])/(2GraphData[{"CompleteBipartite",{6,6}},"AutomorphismCount"]))

GraphData[{"CompleteBipartite",{6,6}},"GracefulLabelings"]

solution #1
  0  1  4  5  8  9
 10 12 22 24 34 36

solution #2
  0  1  6  7 12 13
 14 16 18 32 34 36

solution #3
  0  1 12 13 24 25
 26 28 30 32 34 36

solution #4
  0  1  2  9 10 11
 12 15 18 30 33 36

solution #5
  0  1  2 18 19 20
 21 24 27 30 33 36

solution #6
  0  1  2  6  7  8
  9 12 21 24 33 36

solution #7
  0  1  2  3  4  5
  6 12 18 24 30 36

A337793(6) = 14515200
        0.16 real         0.16 user         0.00 sys

fundorig=Flatten[Transpose[Partition[#,6]]]&/@{{0,1,4,5,8,9,10,12,22,24,34,36},{0,1,6,7,12,13,14,16,18,32,34,36},{0,1,12,13,24,25,26,28,30,32,34,36},{0,1,2,9,10,11,12,15,18,30,33,36},{0,1,2,18,19,20,21,24,27,30,33,36},{0,1,2,6,7,8,9,12,21,24,33,36},{0,1,2,3,4,5,6,12,18,24,30,36}}

gs=Function[lab,SetProperty[GraphData[gn={"CompleteBipartite",{6,6}}],VertexLabels->MapIndexed[#2[[1]]->#&,lab]]]/@fundorig

GracefullyLabeledGraphQ/@gs

GraphData[gn,"GracefulLabelingCount"]

Sort[fundorig]

(fund=GracefulLabelingsReduce[GraphData[gn],GracefulLabelingsExpand[GraphData[gn],fundorig]])//Timing

MaxMemoryUsed[]/10^9. GB

fund===Sort[fundorig]

gs=Function[lab,SetProperty[GraphData[gn={"CompleteBipartite",{6,6}}],VertexLabels->MapIndexed[#2[[1]]->#&,lab]]]/@fund

GracefullyLabeledGraphQ/@gs

(Subscript[K, 7,7]) (2 fundamental labelings)

GraphData[{"CompleteBipartite",{7,7}},"GracefulLabelingCount"]

((GraphData[{"CompleteBipartite",{7,7}},"GracefulLabelingCount"])/(2GraphData[{"CompleteBipartite",{7,7}},"AutomorphismCount"]))

GraphData[{"CompleteBipartite",{7,7}},"GracefulLabelings"]

solution #1
  0  1  2  3  4 47 48
  9 16 23 30 37 44 49

solution #2
  0  1  2  3  4  5  6
  7 14 21 28 35 42 49

A337793(7) = 203212800
        9.17 real         9.10 user         0.03 sys

fundorig=Join@@@Partition[ImportString["  0  1  2  3  4 47 48
  9 16 23 30 37 44 49
  0  1  2  3  4  5  6
  7 14 21 28 35 42 49","Table"],2]

orderedfundorig=Flatten[Transpose[Partition[#,7]]]&/@fundorig

gs=Function[lab,SetProperty[GraphData[gn={"CompleteBipartite",{7,7}}],VertexLabels->MapIndexed[#2[[1]]->#&,lab]]]/@orderedfundorig

GracefullyLabeledGraphQ/@gs

(Subscript[K, 8,8]) (10 fundamental labelings)

GraphData[{"CompleteBipartite",{8,8}},"GracefulLabelingCount"]

((GraphData[{"CompleteBipartite",{8,8}},"GracefulLabelingCount"])/(2GraphData[{"CompleteBipartite",{8,8}},"AutomorphismCount"]))

GraphData[{"CompleteBipartite",{8,8}},"GracefulLabelings"]

solution #1
  0  1  4  5 16 17 20 21
 22 24 30 32 54 56 62 64

solution #2
  0  1  4  5 32 33 36 37
 38 40 46 48 54 56 62 64

solution #3
  0  1  4  5  8  9 12 13
 14 16 30 32 46 48 62 64

solution #4
  0  1  8  9 16 17 24 25
 26 28 30 32 58 60 62 64

solution #5
  0  1  8  9 32 33 40 41
 42 44 46 48 58 60 62 64

solution #6
  0  1 16 17 32 33 48 49
 50 52 54 56 58 60 62 64

solution #7
  0  1  2  3 16 17 18 19
 20 24 28 32 52 56 60 64

solution #8
  0  1  2  3 32 33 34 35
 36 40 44 48 52 56 60 64

solution #9
  0  1  2  3  8  9 10 11
 12 16 28 32 44 48 60 64

solution #10
  0  1  2  3  4  5  6  7
  8 16 24 32 40 48 56 64

A337793(8) = 65028096000
      522.10 real       519.64 user         0.67 sys

fundorig=Join@@@Partition[ImportString["  0  1  4  5 16 17 20 21
 22 24 30 32 54 56 62 64
  0  1  4  5 32 33 36 37
 38 40 46 48 54 56 62 64
  0  1  4  5  8  9 12 13
 14 16 30 32 46 48 62 64
  0  1  8  9 16 17 24 25
 26 28 30 32 58 60 62 64
  0  1  8  9 32 33 40 41
 42 44 46 48 58 60 62 64
  0  1 16 17 32 33 48 49
 50 52 54 56 58 60 62 64
  0  1  2  3 16 17 18 19
 20 24 28 32 52 56 60 64
  0  1  2  3 32 33 34 35
 36 40 44 48 52 56 60 64
  0  1  2  3  8  9 10 11
 12 16 28 32 44 48 60 64
  0  1  2  3  4  5  6  7
  8 16 24 32 40 48 56 64","Table"],2]

orderedfundorig=fundorig

gs=Function[lab,SetProperty[GraphData[gn={"CompleteBipartite",{8,8}}],VertexLabels->MapIndexed[#2[[1]]->#&,lab]]]/@orderedfundorig

GracefullyLabeledGraphQ/@gs

(Subscript[K, 9,9]) (3 fundamental labelings)

GraphData[{"CompleteBipartite",{9,9}},"GracefulLabelingCount"]

((GraphData[{"CompleteBipartite",{9,9}},"GracefulLabelingCount"])/(2GraphData[{"CompleteBipartite",{9,9}},"AutomorphismCount"]))

GraphData[{"CompleteBipartite",{9,9}},"GracefulLabelings"]

solution #1
  0  1  2  9 10 11 18 19 20
 21 24 27 48 51 54 75 78 81

solution #2
  0  1  2 27 28 29 54 55 56
 57 60 63 66 69 72 75 78 81

solution #3
  0  1  2  3  4  5  6  7  8
  9 18 27 36 45 54 63 72 81

A337793(9) = 1580182732800
    29718.94 real     29583.97 user        73.86 sys

fundorig=Join@@@Partition[ImportString["  0  1  2  9 10 11 18 19 20
 21 24 27 48 51 54 75 78 81
  0  1  2 27 28 29 54 55 56
 57 60 63 66 69 72 75 78 81
  0  1  2  3  4  5  6  7  8
  9 18 27 36 45 54 63 72 81","Table"],2]

orderedfundorig=fundorig

gs=Function[lab,SetProperty[GraphData[gn={"CompleteBipartite",{9,9}}],VertexLabels->MapIndexed[#2[[1]]->#&,lab]]]/@orderedfundorig

GracefullyLabeledGraphQ/@gs

(Subscript[K, 10,10]) (??? fundamental labelings)

Running for

27162 60/86400.

CPU-days on byblis67 as of Oct. 21, 2020 without finding any labeling

GraphData[{"CompleteBipartite",{10,10}},"GracefulLabelingCount"]

((GraphData[{"CompleteBipartite",{10,10}},"GracefulLabelingCount"])/(2GraphData[{"CompleteBipartite",{10,10}},"AutomorphismCount"]))

GraphData[{"CompleteBipartite",{10,10}},"GracefulLabelings"]

GraphData

GraphClassString

GraphClassString[GraphData["CompleteBipartite"]]

GraphDataString

kbig=Sort[Flatten[Table[{m,n},{n,11,20},{m,2,n-1}],1]]

Length[kbig]

Select[kbig,Head[ToEntity[System`CompleteGraph[#]]]=!=ToEntity&]

file=OpenWrite["~/Kmn.m"]

Function[{k,n},WriteString[file,GraphDataString[System`CompleteGraph[{k,n}],
"Name"->"("<>ToString[k]<>","<>ToString[n]<>")-complete bipartite graph",
"StandardName"->{"CompleteBipartite",{k,n}},
"AlternateStandardNames"->{"K"<>ToString[k]<>","<>ToString[n]},
"Classes"->{"CompleteBipartite"},
"NotationRules"->{"CompleteBipartite"->{k,n}},
"Notation"->HoldForm[Subscript["K",Sequence[k,n]]],
"Information"->"CompleteBipartiteGraph",
"Skip"->{"Arboricity","CliqueCoveringNumber","ConnectedDominatingSets"},
	(*bug(338571):TimeConstrained Subgraph sporadically crashes kernel after multiple evaluations*)
TimeConstraint->10,
Debug->True
]]]@@@kbig;

Close[file]

GraphData file Property sizes

Length[lines=ReadList["/Users/eww/Kmn.m","String",NullRecords->True]]//Timing

data=Reverse@Sort[MapIndexed[{StringLength[#],#2,StringTake[#,UpTo[50]]}&,lines]]

Take[data,20]//Column