Lemke Graph

Author

Eric W. Weisstein
July 15, 2018

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

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

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

Sources

Hurlbert 2011

https://arxiv.org/pdf/1101.5641.pdf

Hurlbert 2013

G. Hurlbert, General graph pebbling, Discrete Appl. Math. 161, 2013, 1221-1231

Lemke and Kleitman 1989

P. Lemke, D.J. Kleitman, An addition theorem on the integers modulo n, J. Number Theory 31 (1989) 335–345. MR0993907

Properties

GraphData["LemkeGraph"]//StyleGraphs

GraphData["LemkeGraph",{"V","M"}]

Construction

Graphics[{MapIndexed[Text[#2[[1]],#]&,c=CirclePoints[5]]}]

g=System`Graph[Range[8],UndirectedEdge@@@{{1,2},{1,3},{2,7},{7,8},{3,6},{3,8},{3,4},{4,5},{5,6},{6,7},{5,8},{5,7},{4,7}},VertexCoordinates->Join[{c[[1]]-{0,1},c[[5]]-{0,1}},c,{{0,0}}],VertexLabels->"Name"]

GraphIndex[g]

System`Graph[Range[8],UndirectedEdge@@@{{1,2},{1,3},{2,7},{7,8},{3,6},{3,8},{3,4},{4,5},{5,6},{6,7},{5,8},{5,7},{4,7}}]

System`Graph[UndirectedEdge@@@{{1,2},{1,3},{2,7},{7,8},{3,6},{3,8},{3,4},{4,5},{5,6},{6,7},{5,8},{5,7},{4,7}}]

Square (GraphCartesianProductOfLemkeGraphs)

lsquared=GraphCartesianProduct[g,g]

lsquared//VertexCount

lsquared//RecognizeGraph

lsquared//GraphDiameter

GraphData

GraphDataClassString

GraphDataClassString["LemkeGraph"]

GraphDataString

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

WriteString[file,GraphDataString[lsquared,
"StandardName"->"GraphCartesianProductOfLemkeGraphs",
"Name"->"graph Cartesian product of Lemke graphs",
"TimeConstraint"->10,
Debug->True]]

Close[file]