Circuit Rank

Author

Eric W. Weisstein
May 10, 2019

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

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

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

Upper inequality

μ≤ν≤(2^μ)-1

“Essentially only 4 graphs satisfying the upper equality”: (Subscript[K, 3]), (Subscript[K, 4]), (Subscript[K, 3,3]), (Subscript[K, 4])-e

GraphData["DiamondGraph","Notation"]//TraditionalForm

Select[GraphData["UndirectedCycleCount","Defined"],GraphData[#,"UndirectedCycleCount"]<GraphData[#,"CyclomaticNumber"]&]

Select[GraphData["UndirectedCycleCount","Defined"],GraphData[#,"UndirectedCycleCount"]>2^GraphData[#,"CyclomaticNumber"]-1&]

(wrong; fixed)

Huh?

bad=Select[GraphData["UndirectedCycleCount","Defined"],GraphData[#,"UndirectedCycleCount"]==2^GraphData[#,"CyclomaticNumber"]-1&]

GraphData/@Take[bad,10]

Parametrized families

Andrasfai

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

FindSequenceFunction[seq,n]//Factor

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"CyclomaticNumber"],{n,10}]

Antiprism

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

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

FindSequenceFunction[seq,n-2]//Factor

Apollonian

seq=Table[GraphData[{"Apollonian",n},"CyclomaticNumber"],{n,6}]

FindSequenceFunction[seq,n]

Barbell

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

FindSequenceFunction[seq,n-2]//Factor

Bishop n×n

A143941

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

FindLinearRecurrence[seq]

Table[n*(1+6*n+2*n^2)/3,{n,10}]

BlackBishop n×n

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

FindSequenceFunction[Drop[seq,2],n-2]

FindGeneratingFunction[seq,x]

Book

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

Bruhat

A317483

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

FindSequenceFunction[seq,n]

Table[(n-3)n!/2+1,{n,10}]

seq=Table[(n-3)n!/2+1,{n,20}]

FindLinearRecurrence[Drop[seq,3]]//Head

FindGeneratingFunction[seq,x]//Head//Timing

Centipede

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

CocktailParty

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

FindSequenceFunction[Rest@seq,n-1]//Factor

Complete

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

seq=Table[GraphData[{"Complete",n},"CyclomaticNumber"],{n,20}]

FindSequenceFunction[seq,n]//Factor

CompleteBipartite m×n

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

CompleteBipartite n×n

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

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

FindSequenceFunction[seq,n]//Factor

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

CrossedPrism

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

FindSequenceFunction[seq,n-1]//Factor

Crown

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

FindSequenceFunction[seq,n-2]//Factor

CubeConnectedCycle

A005183

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

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

FindSequenceFunction[seq,n-2]//FullSimplify

Cycle

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

seq=Table[GraphData[{"Cycle",n},"CyclomaticNumber"],{n,3,20}]

DiagonalIntersection

A007678

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

FindSequenceFunction[seq,n-2]

del[m_,n_]:=If[Mod[n,m]==0,1,0];R[n_]:=If[n<3,0,(n^4-6n^3+23n^2-42n+24)/24+del[2,n](-5n^3+42n^2-40n-48)/48-del[4,n](3n/4)+del[6,n](-53n^2+310n)/12+del[12,n](49n/2)+del[18,n]*32n+del[24,n]*19n-del[30,n]*36n-del[42,n]*50n-del[60,n]*190n-del[84,n]*78n-del[90,n]*48n-del[120,n]*78n-del[210,n]*48n];Table[R[n],{n,1,20}]

Dipyramid

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

FindSequenceFunction[seq,n-2]//Factor

Empty

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

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

FibonacciCube

A006478

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

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

Table[1+(2 (n+1) Fibonacci[n]+n Fibonacci[n+1])/5-Fibonacci[n+2],{n,20}]

LinearRecurrence[{3,-1,-3,1,1},{0,0,1,3,8},20]

CoefficientList[Series[1/((1-x) (1-x-x^2)^2),{x,0,50}],x]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"CyclomaticNumber"],{n,10}]

FoldedCube

A002064

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

FindSequenceFunction[Rest@seq,n-2]//FullSimplify

Gear

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

FindSequenceFunction[seq,n-2]//Factor

GeneralizedPetersen

Grid m×n

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

Grid n×n

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

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

FindSequenceFunction[seq,n]

Grid k×m×n

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

Grid n×n×n

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

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

HalvedCube

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

FindSequenceFunction[Rest@seq,n-1]//FullSimplify

Hanoi

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

FindSequenceFunction[seq,n]

Helm

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

FindSequenceFunction[DeleteMissing@seq,n-2]

Hypercube

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

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

FindSequenceFunction[seq,n+1]//FullSimplify

Keller

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

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

King m×n

Table[GraphData[{"King",{m,n}},"CyclomaticNumber"],{n,10},{m,n}]//Column

Table[3(m-1)(n-1),{n,10},{m,n}]//Column

King n×n

seq=Table[GraphData[{"King",{n,n}},"CyclomaticNumber"],{n,10}]

FindSequenceFunction[seq,n]

Knight m×n

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

Table[GraphData[{"Knight",{m,n}},"CyclomaticNumber"],{n,10},{m,n}]//Column

Knight n×n

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

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

FindSequenceFunction[Drop[seq,3],n-3]//Factor

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

seq=Table[GraphData[{"MoebiusLadder",n},"CyclomaticNumber"],{n,3,20}]

Mycielski

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

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

FindSequenceFunction[Rest@seq,n-1]//FullSimplify

Odd

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

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

FindSequenceFunction[seq,n]

FindSequenceFunction[Drop[seq,2],n-2]

FindGeneratingFunction[seq,x]

Pan

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

Path

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

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

Prism

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

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

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"CyclomaticNumber"],{n,10}]

FindSequenceFunction[seq,n]//Factor

Rook m×n

Table[GraphData[{"Rook",{m,n}},"CyclomaticNumber"],{n,10},{m,n}]//Column

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"CyclomaticNumber"],{n,10}]

FindSequenceFunction[seq,n]//Factor

RookComplement n×n

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

FindSequenceFunction[Drop[seq,2],n-2]//Factor

SierpinskiCarpet

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

FindSequenceFunction[seq,n]

SierpinskiSieve

seq=Table[GraphData[{"SierpinskiSieve",n},"CyclomaticNumber"],{n,5}]

FindSequenceFunction[seq,n]

SierpinskiTetrahedron

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

FindSequenceFunction[seq,n]

Star

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

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

Sun

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

FindSequenceFunction[seq,n-2]//Factor

Sunlet

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

FindSequenceFunction[seq,n-2]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"CyclomaticNumber"],{n,6,10}]

FindSequenceFunction[seq,n-5]

Transposition

A173038

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

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

Triangular

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

FindSequenceFunction[seq,n-1]//Factor

TriangularGrid

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

FindSequenceFunction[seq,n+1]

TriangularHoneycombAcuteKnight

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

FindSequenceFunction[Drop[seq,1],n-1]

TriangularHoneycombBishop

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

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombObtuseKnight

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

FindSequenceFunction[Drop[seq,5],n-5]//Factor

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[x (((x^4) (-5-x+(x^3)))/(((-1+x))^3)),{x,0,n}],n>0]//Factor

TriangularHoneycombQueen

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

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombRook

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

FindSequenceFunction[seq,n]

Web

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

FindSequenceFunction[seq,n-2]

Wheel

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

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

WhiteBishop n×n

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

FindSequenceFunction[seq,n-1]