Unswitchable Graph

Author

Eric W. Weisstein
May 24, 2023

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

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

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

Sources

Mukhopadhyay, A.; John, D.; and Vasudevan, S.  "Recognizing and Generating Unswitchable Graphs."  12 Apr 2023.  https://arxiv.org/abs/2304.12381

Classes

Unswitchable graphs are a proper subclass of split graphs. ->All unswitchable graphs are split

data={#,UnswitchableGraphQ[GraphData[#]],GraphData[#,"Split"]}&/@GraphData[;;10];

Cases[data,{_,True,False}]

Switchable graphs may be split or not split:

Cases[data,{_,False,split_}:>split]//Union

Counts

Unswitchable connected

Table[Count[ConnectedGraphs[n],_?UnswitchableGraphQ],{n,8}]

GraphicsGrid[Flatten[Partition[#,UpTo[4]]&/@Table[
Show[
StyleGraphs[GraphData[#],VertexSize->If[#==="SingletonGraph",.015,{"Scaled",.05}]],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[14,Black,Italic,FontFamily->"Times"]],PageWidth->100,TextAlignment->Center]]&/@Select[GraphData["Connected",n],UnswitchableGraphQ[GraphData[#]]&],{n,5}
],1],Dividers->{{Thick,{True},Thick},{{Thick},True,Thick}},ImageSize->600,Alignment->Top]

Unswitchable simple

Table[Count[Graphs[n],_?UnswitchableGraphQ],{n,8}]

GraphicsGrid[Flatten[Partition[#,UpTo[6]]&/@Table[
Show[
StyleGraphs[GraphData[#],VertexSize->{"Scaled",.04}],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[Black,Italic,FontFamily->"Times"]]],TextAlignment->Center]&/@Select[GraphData[n],UnswitchableGraphQ[GraphData[#]]&],{n,5}
],1],Dividers->All,ImageSize->700,Alignment->Top]

Examples

Mukhopadhyay, A.; John, D.; and Vasudevan, S.  "Recognizing and Generating Unswitchable Graphs."  12 Apr 2023.  https://arxiv.org/abs/2304.12381

{"CompleteKPartite", {1, 1, 1, 3}}: split, unswitchable

v=Join[CirclePoints[3],CirclePoints[1/2,3]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[2,6,4,2,5,3,4,5,6,1,5],{3,6},{1,4}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

g=GraphData[{"CompleteKPartite",{1,1,1,3}}];

<<MathWorld`Graphs`

SplitGraphQ[g]

UnswitchableGraphQ[g,Debug->True]

Net graph: split, switchable

g=GraphData["NetGraph"]

{SplitGraphQ[g],UnswitchableGraphQ[g]}

UnswitchableGraphQ[g,Debug->True]

Example: not split, switchable

v={{361.8911374204601`,330.1950715859032`},{123.39945086882035`,428.31858021292226`},{96.11860621634848`,259.1981843489966`},{200.49857745961822`,351.2277900146844`},{42.0862778389623`,332.6167936245718`},{214.0202061918747`,482.7177098629467`},{148.31692823054328`,99.66880812530599`},{412.77647760646107`,132.13905714635348`},{583.1848461209006`,432.1324798091043`},{472.00654674498287`,508.6105451541851`},{241.02594988986783`,196.4001391948117`},{588.1575042829172`,297.9040550048949`}}/600;
g=Graph[Range[0,11],UndirectedEdge@@@{e[6,7,11,8,9,5,1,4,6,2,1,0,10,2,4,5,3,10],e[4,3,0,8],{9,11},{0,7},{1,3},{2,5}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

SplitGraphQ[g]

UnswitchableGraphQ[g]

Parametrized families

Alkane

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

AlternatingGroupGraph

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

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Unswitchable"],{n,10}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Unswitchable"],{n,15}]

Antiprism

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

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

Apollonian

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

Barbell

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

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Unswitchable"],{n,10}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Unswitchable"],{n,10}]

Book

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

Bruhat

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

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Unswitchable"],{n,10}]

Centipede

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

CocktailParty

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

Complete

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

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

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

CompleteBipartite m×n

val=Entity["Graph",{"CompleteBipartite",{m,n}}]["Unswitchable"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Unswitchable"],
val
},{n,20},{m,n}],1],{_,x_,x_}]

Cases[
Flatten[Table[{{m,n},GraphData[{"CompleteBipartite",{m,n}},"Switchable"]},{n,20},{m,n}],1],{ind_,False}:>ind]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

val=Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Unswitchable"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Unswitchable"],
val
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

Cases[Flatten[Table[{{k,m,n},GraphData[{"CompleteTripartite",{k,m,n}},"Switchable"]},{n,10},{m,n},{k,m}],2],{ind_,False}:>ind]

CompleteTripartite n×n×n

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

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

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"Unswitchable"],{n,2,10}]

Crown

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

CubeConnectedCycle

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

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

Cycle

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

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

CycleComplement

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

DiagonalIntersection

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

Dipyramid

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

DoubleCone

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

Empty

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

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

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

FibonacciCube

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

Flower

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

FoldedCube

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

Gear

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

Giraffe n×n

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

Goldberg

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

Grid m×n

val=Entity["Graph",{"Grid",{m,n}}]["Unswitchable"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"Unswitchable"],
val
},{n,10},{m,n}],1],{_,x_,x_}]

Cases[Flatten[Table[{{m,n},GraphData[{"Grid",{m,n}},"Switchable"]},{n,10},{m,n}],1],{ind_,False}:>ind]

Grid n×n

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

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

Grid k×m×n

val=Entity["Graph",{"Grid",{k,m,n}}]["Unswitchable"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Unswitchable"],
val
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

data=Flatten[Table[{{k,m,n},GraphData[{"Grid",{k,m,n}},"Switchable"]},{n,5},{m,n},{k,m}],2]

Cases[data,{ind_,False}:>ind]

Grid n×n×n

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

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

HalvedCube

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

Hanoi

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

Helm

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

Hypercube

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

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

Keller

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

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

King n×n

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

Knight m×n

val=Entity["Graph",{"Knight",{m,n}}]["Unswitchable"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"Unswitchable"],
val
},{n,10},{m,n}],1],{_,x_,x_}]

Cases[Flatten[Table[{{m,n},GraphData[{"Knight",{m,n}},"Switchable"]},{n,10},{m,n}],1],{ind_,False}:>ind]

Knight n×n

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

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

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

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

Path

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

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

PathComplement

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

Prism

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

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

Queen n×n

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

Rook n×n

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

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Unswitchable"],{n,10}]

SierpinskiCarpet

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

Spoke n×n

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

StackedBook

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

StackedPrism

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

Star

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

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

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

Sun

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

Sunlet

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

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Unswitchable"],{n,3,10}]

Transposition

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

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

Trapezohedron

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

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

Triangular

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

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"Unswitchable"],{n,0,10}]

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Unswitchable"],{n,9}]

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Unswitchable"],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Unswitchable"],{n,10}]

TriangularSnake

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

Web

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

Wheel

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

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

WheelComplement

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

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Unswitchable"],{n,2,10}]

Zebra n×n

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

Algorithms

VertexDegrees

Select[GraphData[;;5],UnswitchableGraphQ[GraphData[#],Method->"VertexDegrees"]&]

DeleteCases[Monitor[{
gn=#,
GraphData[#,"Unswitchable"],
UnswitchableGraphQ[GraphData[#],Method->"VertexDegrees"]
}&/@GraphData[;;10],gn],
{_,x_,x_}
]//Timing

Forbidden induced subgraphs

DeleteCases[Monitor[{
gn=#,
GraphData[#,"Unswitchable"],
UnswitchableGraphQ[GraphData[#],Method->"ForbiddenSubgraphs"]
}&/@GraphData[;;10],gn],
{_,x_,x_}
]//Timing

Select[GraphData[;;5],UnswitchableGraphQ[GraphData[#],Method->"ForbiddenSubgraphs"]&]

Select[GraphData[;;5],UnswitchableGraphQ[GraphData[#],Method->"ForbiddenSubgraphs"]&]