Pretzel Graph

Author

Eric W. Weisstein
May 17, 2023

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

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

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

Examples

pretzel=Sort[GraphData[#,{"V","#"}]&/@GraphData["Pretzel"]]

Grid[pretzel,Dividers->All,Alignment->{{{Decimal},Left}}]

Figure

GraphicsGrid[Map[Show[StyleGraphs[GraphData[#]],PlotLabel->Style[GraphData[#,"Name"],Directive[Black,Italic,FontFamily->"Times"]]]&,SplitBy[pretzel,First][[All,All,2]],{2}],ImageSize->400,Dividers->All]

Parametrized families

Antiprism

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

Table[GraphData[{"Antiprism",n},"Pretzel"],{n,3,25}]//Union

Complete

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

seq=Table[GraphData[{"Complete",n},"Pretzel"],{n,30}]

Position[seq,True]//Flatten

Graph genus:

A000933

data=Table[Piecewise[{{Ceiling[(n-3)(n-4)/12],n>2}}],{n,20}]

Pretzel:

Position[data,3]//Flatten

CompleteBipartite m×n

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

The following is the graph genus:

Grid[data={#[[1,2]],#[[All,1]]}&/@SplitBy[SortBy[Flatten[Table[{{m,n},Ceiling[(m-2)(n-2)/4]},{n,2,20},{m,2,n}],1],Last],Last],Dividers->All,Alignment->Left]

Pretzel:

pretzel=FirstCase[data,{3,c_}:>c]

GraphData[{"CompleteBipartite",#},"Pretzel"]&/@pretzel

Reduce[Ceiling[(m-2)(n-2)/4]==3&&m≤n,{m,n},PositiveIntegers,Backsubstitution->True]

CompleteBipartite n×n

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

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

Position[seq,True]//Flatten

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Pretzel"]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Pretzel"]

seq=Table[GraphData[{"Complete",n},"Pretzel"],{n,10}]

Position[seq,True]//Flatten

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["Pretzel"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"Pretzel"],{n,3,8}]

Cycle

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

seq=Table[GraphData[{"Cycle",n},"Pretzel"],{n,3,30}]//Union

Empty

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

Table[GraphData[{"Empty",n},"Pretzel"],{n,30}]//Union

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["Pretzel"]

GraphData[#,"Pretzel"]&/@Select[GraphData["Grid"],Length[GraphData[#,"NotationRules","Grid"]]==2&]//Union

Grid n×n

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

Table[GraphData[{"Grid",{n,n}},"Pretzel"],{n,20}]//Union

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["Pretzel"]

GraphData[#,"Genus"]&/@Select[GraphData["Grid"],Length[GraphData[#,"NotationRules","Grid"]]==3&]//Union

GraphData[#,"Pretzel"]&/@Select[GraphData["Grid"],Length[GraphData[#,"NotationRules","Grid"]]==3&]//Union

Grid n×n×n

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

Table[GraphData[{"Grid",{n,n,n}},"Genus"],{n,10}]

Table[GraphData[{"Grid",{n,n,n}},"Pretzel"],{n,10}]

Hypercube

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

seq=Table[GraphData[{"Hypercube",n},"Pretzel"],{n,0,10}]

Position[seq,True]-1//Flatten

Graph genus:

A000337

data=Table[Piecewise[{{1+(n-4)(2^(n-3)),n>1}}],{n,20}]

Pretzel:

Position[data,3]//Flatten

Keller

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

seq=Table[GraphData[{"Keller",n},"Genus"],{n,5}]

seq=Table[GraphData[{"Keller",n},"Pretzel"],{n,5}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["Pretzel"]

GraphData[#,"Genus"]&/@GraphData["Knight"]

GraphData[#,"Pretzel"]&/@GraphData["Knight"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["Pretzel"]

Table[GraphData[{"Knight",{n,n}},"Genus"],{n,20}]

Table[GraphData[{"Knight",{n,n}},"Pretzel"],{n,20}]

Ladder

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

Table[GraphData[{"Ladder",n},"Pretzel"],{n,20}]//Union

MoebiusLadder

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

seq=Table[GraphData[{"MoebiusLadder",n},"Pretzel"],{n,3,25}]//Union

Mycielski

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

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

seq=Table[GraphData[{"Mycielski",n},"Pretzel"],{n,11}]

Position[seq,True]//Flatten

Odd

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

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

seq=Table[GraphData[{"Odd",n},"Pretzel"],{n,7}]

Path

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

seq=Table[GraphData[{"Path",n},"Pretzel"],{n,20}]//Union

Prism

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

seq=Table[GraphData[{"Prism",n},"Pretzel"],{n,3,25}]//Union

Star

Entity["Graph",{"Star",n}]["Pretzel"]

seq=Table[GraphData[{"Star",n},"Pretzel"],{n,25}]//Union

Transposition

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

seq=Table[GraphData[{"Transposition",n},"Genus"],{n,6}]

seq=Table[GraphData[{"Transposition",n},"Pretzel"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["Pretzel"]

seq=Table[GraphData[{"Trapezohedron",n},"Pretzel"],{n,3,20}]//Union

Wheel

Entity["Graph",{"Wheel",n}]["Pretzel"]

seq=Table[GraphData[{"Wheel",n},"Pretzel"],{n,4,20}]//Union