Necklace Graph

Author

Eric W. Weisstein
February 7, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/NecklaceGraph.nb.

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

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

Figure

<<MathWorld`Graphs`

GraphicsRow[StyleGraphs@Table[NecklaceGraph[n,PlotLabel->n],{n,5}],
Dividers->All,Alignment->Top,
BaseStyle->InsetBoxOptions->{BaseStyle->Directive[LightDarkSwitched@Black,14,FontFamily->"Times"]}]

Sources

http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/#/neck

https://aimath.org/WWN/matrixspectrum/catalog2.html

[DG+09] L. DeAlba, J. Grout, L. Hogben, R. Mikkelson, and K. Rasmussen. Universally optimal matrices and field independence of the minimum rank of a graph. Elec. J. Lin. Alg., 18: 403–419, 2009.

Construction

NecklaceGraph[n_,opts___?OptionQ]:=Module[
{
v,
ee,
c=CirclePoints[{1,Pi/2},3n]
},
v=Join[c,3/2c[[1;;;;3]]];
ee=Sort[Sort/@Join[
Partition[Range[3n],2,1,1],
Flatten[Thread/@Transpose[{Range[3n+1,3n+n],Partition[RotateRight[Range[3n]],3]}],1]
]];
Graph[
Range[4n],
UndirectedEdge@@@ee,
VertexCoordinates->v,
opts
]
]

gs=Table[NecklaceGraph[n],{n,10}]

CubicGraphQ/@gs

RecognizeGraph/@gs

VertexCount/@gs

GraphData

GraphDataString

<<Mathworld`Graphs`

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

Do[WriteString[
file,
GraphDataString[
NecklaceGraph[n],
"StandardName"->{"Necklace",n},
"Name"->ToString[n]<>"\[Hyphen]ncklace graph",
"Clases"->{"Necklace"},
"NotationRules"->{"Necklace"->n},
"MinimumRank"->3n-2,
"MaximumNullity"->n+2,
"ZeroForcingNumber"->n+2,
"Information"->"NecklaceeGraph",
Debug->True,
TimeConstraint->10
]
],{n,4,10}]

Close[file]