Bipartite Double Graph

Author

Eric W. Weisstein
October 19, 2018

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

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

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

Table

Grid[DeleteCases[GraphData["Connected",{"#","BipartiteDoubleGraphName"}],{_,_Missing}],Dividers->All,Alignment->Left]

Parametrized families

Antiprism

Entity["Graph",{"Antiprism",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Antiprism",n},"BipartiteDoubleGraphName"],{n,3,20}]

Complete

Entity["Graph",{"Complete",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Complete",n},"BipartiteDoubleGraphName"],{n,20}]

Cycle

Entity["Graph",{"Cycle",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Cycle",n},"BipartiteDoubleGraphName"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Empty",n},"BipartiteDoubleGraphName"],{n,30}]

FoldedCube

Table[GraphData[{"FoldedCube",n},"BipartiteDoubleGraphName"],{n,2,10}]

GeneralizedPetersen

Entity["Graph",{"GeneralizedPetersen",{n,k}}]["BipartiteDoubleGraphName"]

GeneralizedPetersenIndices[GraphData[{"HoneycombToroidal",{1,40,17}}]]

Grid[Sort[DeleteCases[
{"GeneralizedPetersen"/.GraphData[#,"NotationRules"],GraphData[#,"BipartiteDoubleGraphName"]}&/@GraphData["GeneralizedPetersen"],
{_,{"Prism",_}}
]
],Dividers->All,Alignment->Left]//TraditionalForm

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Grid",{n,n}},"BipartiteDoubleGraphName"],{n,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Hypercube",n},"BipartiteDoubleGraphName"],{n,10}]

Keller

Entity["Graph",{"Keller",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Keller",n},"BipartiteDoubleGraphName"],{n,5}]

BipartiteDoubleGraph[KellerGraph[3]]

ConnectedGraphQ[%]

Kneser

Grid[Sort[{"Kneser"/.GraphData[#,"NotationRules"],#,GraphData[#,"BipartiteDoubleGraphName"]}&/@GraphData["Kneser"]],Dividers->All,Alignment->Left]

Knight

Ladder

Entity["Graph",{"Ladder",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Ladder",n},"BipartiteDoubleGraphName"],{n,20}]

RecognizeGraph/@ConnectedGraphComponents[BipartiteDoubleGraph[LadderGraph[4]]]

LadderRung

Table[GraphData[{"LadderRung",n},"BipartiteDoubleGraphName"],{n,20}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"MoebiusLadder",n},"BipartiteDoubleGraphName"],{n,3,20}]

Mycielski

Entity["Graph",{"Mycielski",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Mycielski",n},"BipartiteDoubleGraphName"],{n,11}]

BipartiteDoubleGraph[MycielskiGraph1[4]]

ConnectedGraphQ[%]

RecognizeGraph[%%]

Odd

Entity["Graph",{"Odd",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Odd",n},"BipartiteDoubleGraphName"],{n,7}]

Path

Entity["Graph",{"Path",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Path",n},"BipartiteDoubleGraphName"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Prism",n},"BipartiteDoubleGraphName"],{n,3,25}]

IsomorphicGraphQ[BipartiteDoubleGraph[g=PrismGraph[8]],GraphDisjointUnion[g,g]]

Sun

Table[GraphData[{"Sun",n},"BipartiteDoubleGraphName"],{n,3,20}]

Sunlet

Table[GraphData[{"Sunlet",n},"BipartiteDoubleGraphName"],{n,3,20}]

Transposition

Entity["Graph",{"Transposition",n}]["BipartiteDoubleGraphName"]

Table[GraphData[{"Transposition",n},"BipartiteDoubleGraphName"],{n,6}]

TranspositionGraph[3]//RecognizeGraph

RecognizeGraph/@ConnectedGraphComponents[BipartiteDoubleGraph[TranspositionGraph[4]]]

RecognizeGraph/@ConnectedGraphComponents[BipartiteDoubleGraph[TranspositionGraph[5]]]

Web

Table[GraphData[{"Web",n},"BipartiteDoubleGraphName"],{n,3,20}]

IsomorphicGraphQ[BipartiteDoubleGraph[WebGraph[11]],WebGraph[22]]

IsomorphicGraphQ[BipartiteDoubleGraph[g=WebGraph[4]],GraphDisjointUnion[g,g]]

Distance-regular

DesarguesGraph: Doubled O3≅Desargues graph

RecognizeGraph/@{
DistanceRegularGraph["http://www.distanceregular.org/graphdata/desargues.am"],
BipartiteDoubleGraph[GraphData[{"Odd",3}]]
}

GraphData["DesarguesGraph","StandardNames"]

KummerGraph: Doubled H(2,4)≅Doubled Shrikhande graph≅Folded 6-cube

RecognizeGraph/@{
DistanceRegularGraph["http://www.distanceregular.org/graphdata/folded-cube6.am"],
BipartiteDoubleGraph[GraphData["ShrikhandeGraph"]]
}

{"BipartiteKneser",{7,3}}: Doubled O4

RecognizeGraph/@{
DistanceRegularGraph["http://www.distanceregular.org/graphdata/doubled-odd4.am"],
BipartiteDoubleGraph[GraphData[{"Odd",4}]]
}

HoffmanSingletonBipartiteDoubleGraph: Doubled Hoffman-Singleton graph

RecognizeGraph/@{
DistanceRegularGraph["http://www.distanceregular.org/graphdata/doubled-hoffmansingleton.am"],
BipartiteDoubleGraph[GraphData["HoffmanSingletonGraph"]]
}

GewirtzBipartiteDoubleGraph: Doubled Gewirtz graph

RecognizeGraph/@{
DistanceRegularGraph["http://www.distanceregular.org/graphdata/doubled-gewirtz.am"],
BipartiteDoubleGraph[GraphData["GewirtzGraph"]]
}

HigmanSimsBipartiteDoubleGraph: Doubled Higman-Sims graph

RecognizeGraph/@{
DistanceRegularGraph["http://www.distanceregular.org/graphdata/doubled-higmansims.am"],
BipartiteDoubleGraph[GraphData["HigmanSimsGraph"]]
}

M22BipartiteDoubleGraph: Doubled M22 graph

RecognizeGraph/@{
DistanceRegularGraph["http://www.distanceregular.org/graphdata/doubled-m22graph.am"],
BipartiteDoubleGraph[GraphData["M22Graph"]]
}

{"BipartiteKneser",{9,4}}: Doubled O5

RecognizeGraph/@{
DistanceRegularGraph["http://www.distanceregular.org/graphdata/doubled-odd5.am"],
BipartiteDoubleGraph[GraphData[{"Odd",5}]]
}

IsomorphicGraphQ[BipartiteDoubleGraph[GraphData[{"Odd",5}]],BipartiteKneserGraph[9,4]]

GraphData[{"BipartiteKneser",{7,3}},"Name"]

file=OpenWrite["~/h94.m"]

WriteString[file,GraphDataString[IndexGraph[BipartiteKneserGraph[9,4]],
"StandardName"->{"BipartiteKneser",{9,4}},
"Name"->"(9,4)\[Hyphen]bipartite Kneser graph",
"Embeddings"->None,
"Information"->"BipartiteKneserGraph",
"Classes"->{"BipartiteKneser","DistanceRegular","DistanceTransitive","Noncirculant","Nongrid"},
"NotationRules"->{"BipartiteKneser"->{9,4},"DistanceRegular"->{{5,4,4,3,3,2,2,1,1},{1,1,2,2,3,3,4,4,5}}},
Debug->True,
TimeConstraint->10]]

Close[file]

{DoubledHalvedLeonardGraph1, DoubledHalvedLeonardGraph2}: Incidence graphs of Leonard semibiplanes [bipartite doubles of the halved Leonard graphs] (2 graphs)

These are the bipartite doubles of the halved Leonard graphs.

g1=DistanceRegularGraph["http://www.distanceregular.org/graphdata/incidence-leonardsemibiplane1.am"];

RecognizeGraph/@(h=HalvedGraphs[GraphData["LeonardGraph"]])

GraphData["Halved*"]

IsomorphicGraphQ@@h

VertexCount/@h

file=OpenWrite["~/halved-leonard.m"];

WriteString[file,GraphDataString[h[[1]],
"StandardName"->"HalvedLeonardGraph1",
"Name"->"first halved Leonard graph",
"Embeddings"->None,
"Information"->None,
"Classes"->{"Noncirculant","Nongrid"},
"Skip"->{"IndependencePolynomial"},
Debug->True,
TimeConstraint->10]]

WriteString[file,GraphDataString[h[[2]],
"StandardName"->"HalvedLeonardGraph2",
"Name"->"second halved Leonard graph",
"Embeddings"->None,
"Information"->None,
"Classes"->{"Noncirculant","Nongrid"},
"Skip"->{"IndependencePolynomial"},
Debug->True,
TimeConstraint->10]]

ds=IndexGraph/@BipartiteDoubleGraph/@h;//Timing

IsomorphicGraphQ[ds[[1]],g1]

g2=DistanceRegularGraph["http://www.distanceregular.org/graphdata/incidence-leonardsemibiplane2.am"];

IsomorphicGraphQ[ds[[2]],g2]

WriteString[file,GraphDataString[ds[[1]],
"StandardName"->"DoubledHalvedLeonardGraph1",
"Name"->"first doubled halved Leonard graph",
"Embeddings"->None,
"Information"->None,
"Classes"->{"Noncirculant","Nongrid"},
"Skip"->{"IndependencePolynomial"},
Debug->True,
TimeConstraint->10]]

WriteString[file,GraphDataString[ds[[2]],
"StandardName"->"DoubledHalvedLeonardGraph2",
"Name"->"second doubled halved Leonard graph",
"Embeddings"->None,
"Information"->None,
"Classes"->{"Noncirculant","Nongrid"},
"Skip"->{"IndependencePolynomial"},
Debug->True,
TimeConstraint->10]]

Close[file]