Graph Square

Author

Eric W. Weisstein
August 15, 2024

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

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

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

Table

TextGrid[
Cases[DeleteCases[{#,GraphData[#,"SquareGraph","Name"]}&/@GraphData[All],{_,_Missing|{"Complete",_}|"TriangleGraph"|"TetrahedralGraph"|"PentatopeGraph"}],{_,_String?(StringFreeQ["+"|"-"|DigitCharacter])}],Dividers->All]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Alkane",n}],{n,10}]

AlternatingGroupGraph

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"AlternatingGroupGraph",n}],{n,2,5}]

Andrasfai

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Andrasfai",n}],{n,20}]

Antelope n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Antelope",{n,n}}],{n,10}]

Antiprism

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Antiprism",n}],{n,3,25}]

Table[IsomorphicGraphQ[GraphPower[GraphData[{"Antiprism",n}],2],CirculantGraph[2n,{1,2,3,4}]],{n,3,25}]

Apollonian

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Apollonian",n}],{n,5}]

Barbell

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Barbell",n}],{n,3,7}]

BlackBishop n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"BlackBishop",{n,n}}],{n,7}]

Bishop n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Bishop",{n,n}}],{n,7}]

Book

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Book",n}],{n,10}]

Bruhat

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Bruhat",n}],{n,4}]

Camel n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Camel",{n,n}}],{n,10}]

Centipede

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Centipede",n}],{n,10}]

CocktailParty

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"CocktailParty",n}],{n,5}]

Complete

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Complete",n}],{n,30}]

Table[GraphData[{"Complete",n},"Diameter"],{n,10}]

CompleteBipartite n×n

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"CompleteBipartite",{n,n}}],{n,10}]

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
RecognizeGraph@GraphPower[GraphData[{"CompleteBipartite",{m,n}}],2],
{"Complete",m+n}
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"CompleteTripartite",{n,n,n}}],{n,5}]

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
RecognizeGraph@GraphPower[GraphData[{"CompleteTripartite",{k,m,n}}],2],
{"Complete",k+m+n}
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"CrossedPrism",2n}],{n,2,12}]

Crown

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Crown",n}],{n,20}]

CubeConnectedCycle

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"CubeConnectedCycle",n}],{n,3,5}]

Cycle

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Cycle",n}],{n,3,10}]

Table[IsomorphicGraphQ[GraphPower[GraphData[{"Cycle",n}],2],CirculantGraph[n,{1,2}]],{n,3,25}]

CycleComplement

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"CycleComplement",n}],{n,3,20}]

DiagonalIntersection

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"DiagonalIntersection",n}],{n,3,14}]

Dipyramid

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Dipyramid",n}],{n,3,20}]

DorogovtsevGoltsevMendes

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"DorogovtsevGoltsevMendes",n}],{n,0,7}]

DoubleCone

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"DoubleCone",n}],{n,3,20}]

Empty

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Empty",n}],{n,30}]

Table[GraphData[{"Empty",n},"SquareGraph","Name"],{n,30}]

FibonacciCube

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"FibonacciCube",n}],{n,15}]

Fiveleaper n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Fiveleaper",{n,n}}],{n,20}]

Flower

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Flower",n}],{n,5,20}]

FoldedCube

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"FoldedCube",n}],{n,2,10}]

Gear

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Gear",n}],{n,3,20}]

Giraffe n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Giraffe",{n,n}}],{n,20}]

Goldberg

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Goldberg",n}],{n,3,20}]

Grid n×n

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Grid",{n,n}}],{n,10}]

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}}],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Grid",{n,n,n}}],{n,5}]

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}}],
XXX
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"HalvedCube",n}],{n,10}]

Hanoi

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Hanoi",n}],{n,6}]

Helm

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Helm",n}],{n,3,20}]

Hypercube

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Hypercube",n}],{n,0,5}]

GraphData[#,"NotationRules","HalvedCube"]&/@%

Keller

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Keller",n}],{n,3}]

King n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"King",{n,n}}],{n,20}]

King m×n

Entity["Graph",{"King",{m,n}}]["SquareGraphName"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}}],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Knight",{n,n}}],{n,10}]

Knight m×n

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

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

Ladder

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Ladder",n}],{n,10}]

LadderRung

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"LadderRung",n}],{n,20}]

LucasCube

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"LucasCube",n}],{n,15}]

MengerSponge

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"MengerSponge",n}],{n,3}]

MoebiusLadder

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"MoebiusLadder",n}],{n,3,25}]

Table[IsomorphicGraphQ[GraphPower[GraphData[{"MoebiusLadder",n}],2],CirculantGraph[2n,{1,2,n-1,n}]],{n,3,25}]

Mycielski

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Mycielski",n}],{n,7}]

CompleteGraphQ[GraphPower[#,2]]&/@Table[GraphData[{"Mycielski",n}],{n,7}]

VertexCount[GraphPower[#,2]]&/@Table[GraphData[{"Mycielski",n}],{n,7}]

Table[Piecewise[{{1,n==1}},3 2^(n-2)-1],{n,7}]

Odd

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Odd",n}],{n,6}]

CompleteGraphQ[GraphPower[#,2]]&/@Table[GraphData[{"Odd",n}],{n,6}]

Pan

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Pan",n}],{n,3,20}]

Path

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Path",n}],{n,10}]

PathComplement

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"PathComplement",n}],{n,20}]

Pell

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Pell",n}],{n,9}]

Prism

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Prism",n}],{n,3,20}]

Table[{2n,{1,4-2Mod[n,2],n-1,n}},{n,3,8}]

CirculantIndices[#,1]&/@Table[GraphPower[GraphData[{"Prism",n}],2],{n,3,10}]

CirculantIndices[GraphPower[GraphData[{"Prism",8}],2],All]

GraphPower[GraphData[{"Prism",8}],2]

GraphPower[PrismGraph[8],2]//RecognizeGraph

adj=AdjacencyMatrix[PrismGraph[8]];

g=SimpleGraph@AdjacencyGraph[adj+adj.adj]

RecognizeGraph@%

CirculantIndices[g]

Queen n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Queen",{n,n}}],{n,20}]

Rook n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Rook",{n,n}}],{n,20}]

RookComplement n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"RookComplement",{n,n}}],{n,20}]

SierpinskiCarpet

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"SierpinskiCarpet",n}],{n,4}]

SierpinskiGasket

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"SierpinskiGasket",n}],{n,7}]

SierpinskiTetrahedron

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"SierpinskiTetrahedron",n}],{n,6}]

Spoke n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Spoke",{n,n}}],{n,5}]

StackedBook

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"StackedBook",{n,n}}],{n,10}]

StackedPrism

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"StackedPrism",{n,n}}],{n,3,5}]

Star

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Star",n}],{n,10}]

Sun

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Sun",n}],{n,3,20}]

Sunlet

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Sunlet",n}],{n,3,20}]

TorusGrid n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"TorusGrid",{n,n}}],{n,3,20}]

Transposition

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Transposition",n}],{n,5}]

CompleteGraphQ[GraphPower[#,2]]&/@Table[GraphData[{"Transposition",n}],{n,5}]

Trapezohedron

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Trapezohedron",n}],{n,3,5}]

Triangular

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Triangular",n}],{n,2,20}]

TriangularGrid

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"TriangularGrid",n}],{n,0,20}]

TriangularHoneycombAcuteKnight

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"TriangularHoneycombAcuteKnight",n}],{n,20}]

TriangularHoneycombBishop

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"TriangularHoneycombBishop",n}],{n,20}]

TriangularHoneycombObtuseKnight

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"TriangularHoneycombObtuseKnight",n}],{n,20}]

TriangularHoneycombQueen

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"TriangularHoneycombQueen",n}],{n,20}]

TriangularHoneycombRook

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"TriangularHoneycombRook",n}],{n,20}]

TriangularSnake

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"TriangularSnake",n}],{n,1,20,2}]

Web

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Web",n}],{n,3,20}]

Wheel

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

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Wheel",n}],{n,4,20}]

WheelComplement

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"WheelComplement",n}],{n,4,20}]

WhiteBishop n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"WhiteBishop",{n,n}}],{n,2,20}]

Zebra n×n

RecognizeGraph[GraphPower[#,2]]&/@Table[GraphData[{"Zebra",{n,n}}],{n,20}]

Tests

l1=Select[GraphData[All],GraphData[#,"Diameter"]≤2&]

SortBy[DeleteCases[{#,GraphData[#,"SquareGraph","Name"]}&/@l1,{_,{"Complete",_}|"SingletonGraph"|{"Path",2}|"TriangleGraph"|"TetrahedralGraph"|"PentatopeGraph"}],GraphData[#[[1]],"V"]&]

DeleteCases[%,{_,_Missing}]

{"CompleteBipartite", {11, 20}}

g=GraphPower[GraphData[{"CompleteBipartite",{11,20}}],2]

CompleteGraphQ[g]

VertexCount[g]

{"Cyclotomic", 31}

g=GraphPower[GraphData[{"Cyclotomic",31}],2]

CompleteGraphQ[g]

VertexCount[g]