Conformally Rigid Graph

Author

Eric W. Weisstein
March 1, 2024

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

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

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

Source

https://arxiv.org/pdf/2402.11758.pdf

Conformally rigid and not edge-transitive

All connected graphs up to 10 nodes

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes"]

SetDirectory[FileNameJoin[{$GraphDataDirectory,"Nodes","ConformallyRigid"}]]

Do[Print[{n,Put[ConformallyRigidGraphQ/@ConnectedGraphs[n],"ConformallyRigid_Connected_"<>If[n<10,"0",""]<>ToString[n]<>".m"]//Timing}],{n,10}]

et=Get/@FileNames["*_Connected*.m","EdgeTransitive"];
dr=Get/@FileNames["*_Connected*.m","DistanceRegular"];
cr=Get/@FileNames["*_Connected*.m","ConformallyRigid"];

Length/@{et,dr,cr}

Table[
Cases[
Transpose[#[[n]]&/@{et,dr,cr}],
{False,False,True}
],{n,10}]

GraphData using SemidefiniteOptimization

special=SortBy[Complement@@GraphData/@{"ConformallyRigid","EdgeTransitive","DistanceRegular"},GraphData[#,"V"]&]

Automatic (MachinePrecision)

data1=Monitor[{
GraphData[gn=#,"V"],
#,
Sequence@@Flatten[ConformallyRigidDualityGap[GraphData[#],WorkingPrecision->10]//Timing//AbsoluteTiming]
}&/@special,
gn];//Timing//AbsoluteTiming

TextGrid[data1,Dividers->All,Alignment->{{Decimal,Left,{Decimal},"×"}}]

"MOSEK"

data2=Monitor[{
GraphData[gn=#,"V"],
#,
Sequence@@Flatten[ConformallyRigidDualityGap[GraphData[#],Method->"MOSEK"]//Timing//AbsoluteTiming]
}&/@special,
gn];//Timing//AbsoluteTiming

TextGrid[data2,Dividers->All,Alignment->{{Decimal,Left,{Decimal},"×"}}]

"FischerBurmeister"

data3=Monitor[{
GraphData[gn=#,"V"],
#,
Sequence@@Flatten[ConformallyRigidDualityGap[GraphData[#],Method->{"FischerBurmeister",WorkingPrecision->30}]//Timing//AbsoluteTiming]
}&/@Drop[special,-1],
gn];//Timing//AbsoluteTiming

TextGrid[data3,Dividers->All,Alignment->{{Decimal,Left,{Decimal},"×"}}]

Preprint

https://arxiv.org/abs/2402.11758

Classes

GraphClassesThatAre["ConformallyRigid"]

Intersection@@(GraphData[#,"Classes"]&/@GraphData["ConformallyRigid"])

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"ConformallyRigid"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"ConformallyRigid"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"ConformallyRigid"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"ConformallyRigid"],{n,20}]

Antiprism

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

Internal`ClearEntityValueCache[]

seq=Table[GraphData[{"Antiprism",n},"ConformallyRigid"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"ConformallyRigid"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"ConformallyRigid"],{n,3,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"ConformallyRigid"],{n,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"ConformallyRigid"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"ConformallyRigid"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"ConformallyRigid"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"ConformallyRigid"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"ConformallyRigid"],{n,10}]

Circulant

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"ConformallyRigid"],{n,20}]

Complete

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

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

https://arxiv.org/abs/2402.11758

CompleteBipartite n×n

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

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

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"ConformallyRigid"],
True
},{n,10},{m,n}],1],{_,x_,x_}]

https://arxiv.org/abs/2402.11758

CompleteTripartite n×n×n

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

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"ConformallyRigid"],{n,10}]

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"ConformallyRigid"],
Piecewise[{{True,k==m==n}},False]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"ConformallyRigid"],{n,2,12}]

Crown

seq=Table[GraphData[{"Crown",n},"ConformallyRigid"],{n,20}]

CubeConnectedCycle

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

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

Cycle

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

seq=Table[GraphData[{"Cycle",n},"ConformallyRigid"],{n,3,30}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

https://arxiv.org/abs/2402.11758

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"ConformallyRigid"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"ConformallyRigid"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"ConformallyRigid"],{n,3,20}]

DistanceRegular

DeleteCases[GraphData[#,{"#","ConformallyRigid"}]&/@GraphData[{"Connected","DistanceRegular"}],{_,True}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"ConformallyRigid"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"ConformallyRigid"],{n,3,20}]

EdgeTransitive

DeleteCases[GraphData[#,{"#","ConformallyRigid"}]&/@GraphData[{"Connected","EdgeTransitive"}],{_,True}]

Empty

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

seq=Table[GraphData[{"Empty",n},"ConformallyRigid"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"ConformallyRigid"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"ConformallyRigid"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"ConformallyRigid"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"ConformallyRigid"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"ConformallyRigid"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"ConformallyRigid"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"ConformallyRigid"],{n,3,20}]

Grid n×n

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

seq=Table[GraphData[{"Grid",{n,n}},"ConformallyRigid"],{n,20}]

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"ConformallyRigid"],
Piecewise[{{True,(Min[m,n]==1&&Max[m,n]<4)||m==n==2}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

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

seq=Table[GraphData[{"Grid",{n,n,n}},"ConformallyRigid"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"ConformallyRigid"],
Piecewise[{{True,k m n<4||k==m==n==2||(k m n==4&&Max[k,m,n]==2)}},False]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"ConformallyRigid"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"ConformallyRigid"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"ConformallyRigid"],{n,3,20}]

Hypercube

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

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

https://arxiv.org/abs/2402.11758

Keller

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

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

King n×n

seq=Table[GraphData[{"King",{n,n}},"ConformallyRigid"],{n,20}]

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"ConformallyRigid"],
Piecewise[{{True,m==n==1}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

seq=Table[GraphData[{"Knight",{n,n}},"ConformallyRigid"],{n,20}]

Knight m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"ConformallyRigid"],
Piecewise[{{True,m==n==1}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

Ladder

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

seq=Table[GraphData[{"Ladder",n},"ConformallyRigid"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"ConformallyRigid"],{n,20}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"ConformallyRigid"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"ConformallyRigid"],{n,3}]

MoebiusLadder

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

seq=Table[GraphData[{"MoebiusLadder",n},"ConformallyRigid"],{n,3,25}]

Mycielski

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

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

Odd

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

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

Pan

seq=Table[GraphData[{"Pan",n},"ConformallyRigid"],{n,3,20}]

Path

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

seq=Table[GraphData[{"Path",n},"ConformallyRigid"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"ConformallyRigid"],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"ConformallyRigid"],{n,9}]

Prism

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

seq=Table[GraphData[{"Prism",n},"ConformallyRigid"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"ConformallyRigid"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"ConformallyRigid"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"ConformallyRigid"],{n,20}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"ConformallyRigid"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"ConformallyRigid"],{n,5}]

SierpinskiSimplex

GraphData[#,"ConformallyRigid"]&/@GraphData["SierpinskiSimplex*"]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"ConformallyRigid"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"ConformallyRigid"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"ConformallyRigid"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"ConformallyRigid"],{n,3,5}]

Star

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

seq=Table[GraphData[{"Star",n},"ConformallyRigid"],{n,25}]

StronglyRegular

DeleteCases[GraphData[#,{"#","ConformallyRigid"}]&/@GraphData[{"Connected","StronglyRegular"}],{_,True}]

Sun

seq=Table[GraphData[{"Sun",n},"ConformallyRigid"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"ConformallyRigid"],{n,3,20}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"ConformallyRigid"],{n,3,20}]

Transposition

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

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

Trapezohedron

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

seq=Table[GraphData[{"Trapezohedron",n},"ConformallyRigid"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"ConformallyRigid"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"ConformallyRigid"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"ConformallyRigid"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"ConformallyRigid"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"ConformallyRigid"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"ConformallyRigid"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"ConformallyRigid"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"ConformallyRigid"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"ConformallyRigid"],{n,3,20}]

Wheel

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

seq=Table[GraphData[{"Wheel",n},"ConformallyRigid"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"ConformallyRigid"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"ConformallyRigid"],{n,2,20}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"ConformallyRigid"],{n,20}]

Algorithms

{"Goldberg", 16}]

GraphData[{"Goldberg",16},{"EdgeTransitive","DistanceRegular","ConformallyRigid"}]

ConformallyRigidGraphQ[GraphData[{"Goldberg",16}]]//Timing//AbsoluteTiming

ConformallyRigidGraphQ[GraphData[{"Goldberg",16}],Method->"MOSEK"]//Timing//AbsoluteTiming

"HoffmanGraph"

GraphData["HoffmanGraph",{"V","M","EdgeTransitive","DistanceRegular","ConformallyRigid"}]

ConformallyRigidGraphQ[GraphData["HoffmanGraph"],Debug->True]//Timing//AbsoluteTiming

ConformallyRigidGraphQ[GraphData["HoffmanGraph"],Method->"MOSEK"]//Timing//AbsoluteTiming

Tests

<<MathWorld`Graphs`

All graph up to 6 vertices

CDSP

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ConformallyRigid"],
ConformallyRigidGraphQ[GraphData[#],WorkingPrecision->Infinity]
}&/@GraphData["Connected",;;6],
gn],
{_,x_,x_}]//Timing//AbsoluteTiming

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ConformallyRigid"],
ConformallyRigidGraphQ[GraphData[#],WorkingPrecision->MachinePrecision]
}&/@GraphData["Connected",;;6],
gn],
{_,x_,x_}]//Timing//AbsoluteTiming

"FischerBurmeister"

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ConformallyRigid"],
Check[res=ConformallyRigidGraphQ[GraphData[#],Method->{"FischerBurmeister",WorkingPrecision->50}],Print[#];res]
}&/@GraphData["Connected",;;6],
gn],
{_,x_,x_}]//Timing//AbsoluteTiming

All graph up to 15 vertices

CDSP

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ConformallyRigid"],
Check[res=ConformallyRigidGraphQ[GraphData[#],WorkingPrecision->Infinity],Print["message from ",#];res]
}&/@GraphData["Connected",;;15],
gn],
{_,x_,x_}]//Timing//AbsoluteTiming

bug(445663): Document, remove, avoid, or otherwise explain Eigenvalues::ssing

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ConformallyRigid"],
ConformallyRigidGraphQ[GraphData[#],WorkingPrecision->MachinePrecision]
}&/@GraphData["Connected",;;15],
gn],
{_,x_,x_}]//Timing//AbsoluteTiming

MOSEK

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ConformallyRigid"],
ConformallyRigidGraphQ[GraphData[#],Method->"MOSEK"]
}&/@GraphData["Connected",;;15],
gn],
{_,x_,x_}]//Timing//AbsoluteTiming

"FischerBurmeister"

ConformallyRigidDualityGap[Graph[{{1,2},{2,3},{3,1}}],Method->{"FischerBurmeister",WorkingPrecision->30}]

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ConformallyRigid"],
Check[res=ConformallyRigidGraphQ[GraphData[#],Method->{"FischerBurmeister",WorkingPrecision->10}],Print[#];res]
}&/@GraphData["Connected",;;15],
gn],
{_,x_,x_}]//Timing//AbsoluteTiming

ConformallyRigidDualityGap of conformally rigid graphs

CDSP

data=Monitor[{
gn=#,
ConformallyRigidDualityGap[GraphData[#],WorkingPrecision->MachinePrecision]
}&/@SortBy[GraphData["ConformallyRigid",;;20],GraphData[#,"V"]&],
gn];//Timing//AbsoluteTiming

Histogram[data[[All,2]]]

data=Monitor[{
gn=#,
ConformallyRigidDualityGap[GraphData[#],WorkingPrecision->Infinity]
}&/@SortBy[GraphData["ConformallyRigid",;;20],GraphData[#,"V"]&],
gn];//Timing//AbsoluteTiming

Histogram[data[[All,2]]]

data=Monitor[{
gn=#,
ConformallyRigidDualityGap[GraphData[#]]
}&/@SortBy[GraphData["ConformallyRigid",;;50],GraphData[#,"V"]&],
gn];//Timing//AbsoluteTiming

MOSEK

data=Monitor[{
gn=#,
ConformallyRigidDualityGap[GraphData[#],Method->"MOSEK"]
}&/@SortBy[GraphData["ConformallyRigid",;;20],GraphData[#,"V"]&],
gn];//Timing//AbsoluteTiming

data[[All,2]]//Union

data=Monitor[{
gn=#,
ConformallyRigidDualityGap[GraphData[#],Method->"MOSEK"]
}&/@SortBy[GraphData["ConformallyRigid",;;50],GraphData[#,"V"]&],
gn];//Timing//AbsoluteTiming

data[[All,2]]//Union

"FischerBurmeister"

ConformallyRigidDualityGap[Graph[{{1,2},{2,3},{3,1}}],Method->{"FischerBurmeister",WorkingPrecision->30}]

data=Monitor[{
gn=#,
ConformallyRigidDualityGap[GraphData[#],Method->{"FischerBurmeister",WorkingPrecision->30}]
}&/@SortBy[GraphData["ConformallyRigid",;;10],GraphData[#,"V"]&],
gn];//Timing//AbsoluteTiming

data[[All,2]]

bug(445601): Histogram[{-1.50418946386504427411274696417*10^-20, ...}] gives a single bin from 0 to 1

Histogram[Rest@data[[All,2]]]