Girth

Author

Eric W. Weisstein
December 26, 2017

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

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

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

Counts

girths=Table[Girth/@Graphs[i],{i,7}];

Min/@girths

Max/@(girths /.∞->0)

First is # of binary forests with n nodes, A3214/M0775

Join[{Count[#,Infinity]&/@girths},
Table[Count[#,i]&/@girths,{i,3,7}]]//ColumnForm

Parametrized family table

GraphDataCountTable["Girth"]

Parametrized families

Andrasfai

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

Antiprism

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

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

Apollonian

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

Bishop n×n

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

BlackBishop n×n

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

Book

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

Centipede

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

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

seq=DeleteCases[Flatten[Table[{{m,n},GraphData[{"CompleteBipartite",{m,n}},"Girth"],Min[m,n]},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

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

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

CompleteTripartite n×n×n

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

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

Crown

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

CubeConnectedCycle

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

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

Cycle

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

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

Empty

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

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

FibonacciCube

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

FoldedCube

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

Gear

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

Grid m×n

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

Block[{m,n},DeleteCases[{#,{m,n}="Grid"/.GraphData[#,"NotationRules"];4,GraphData[#,"Girth"]}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&],{_,x_,x_}]]

Grid n×n

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

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

Grid k×m×n

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

Block[{k,m,n},DeleteCases[{#,{k,m,n}="Grid"/.GraphData[#,"NotationRules"];4,GraphData[#,"Girth"]}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==3&],{_,x_,x_}]]

Grid n×n×n

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

HalvedCube

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

Hanoi

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

Helm

seq=Table[GraphData[{"Helm",n},"Girth"],{n,3,10}]

Hypercube

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

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

King m×n

Block[{m,n},DeleteCases[{#,{m,n}="King"/.GraphData[#,"NotationRules"];3,GraphData[#,"Girth"]}&/@GraphData["King"],{_,x_,x_}]]

King n×n

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

Knight m×n

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

Knight n×n

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

seq=Table[GraphData[{"Knight",{n,n}},"Girth"],{n,10}]

Ladder

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

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

LadderRung

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

MengerSponge

Table[GraphData[{"MengerSponge",n},"Girth"],{n,3}]

gs=Table[MengerSpongeGraph[n],{n,5}];//Timing

TriangleFreeGraphQ/@gs//Timing

SquareFreeGraphQ/@gs//Timing

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

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

FindSequenceFunction[seq,n-2]//FullSimplify

Path

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

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

Prism

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

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

Queen m×n

Block[{m,n},DeleteCases[{#,GraphData[#,"Girth"],{m,n}=("Queen"/.GraphData[#,"NotationRules"]);3}&/@GraphData["Queen"],{_,x_,x_}]]

Queen n×n

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

Rook m×n

Block[{m,n},DeleteCases[{#,GraphData[#,"Girth"],{m,n}=("Rook"/.GraphData[#,"NotationRules"]);3}&/@GraphData["Rook"],{_,x_,x_}]]

Rook n×n

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

RookComplement n×n

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

FindSequenceFunction[seq,n]//FullSimplify

SierpinskiCarpet

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

SierpinskiSieve

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

SierpinskiTetrahedron

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

Star

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

seq=Table[GraphData[{"Star",n},"Girth"],{n,20}]

Sun

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

Sunlet

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

FindSequenceFunction[seq,n-2]

Tetrahedral

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

Transposition

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

Table[GraphData[{"Transposition",n},"Girth"],{n,6}]

Triangular

seq=Table[GraphData[{"Triangular",n},"Girth"],{n,5,20}]

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

Web

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

Wheel

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

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

WhiteBishop n×n

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

Checks

Using Combinatorica

DeleteCases[{GraphData[#,"Girth"],Girth[Graph[#]]}&/@GraphData[;;7],{x_,x_}]//Timing

DeleteCases[{GraphData[#,"Girth"],Girth[Graph[#]]}&/@GraphData[;;10],{x_,x_}]//Timing

Using FindCycle

MyGirth[g_System`Graph]:=Min[Length/@System`FindCycle[GraphData[g],Infinity,All]]

DeleteCases[{GraphData[#,"Girth"],MyGirth[GraphData[#]]}&/@GraphData[;;7],{x_,x_}]//Timing

DeleteCases[{GraphData[#,"Girth"],MyGirth[GraphData[#]]}&/@GraphData[;;10],{x_,x_}]//Timing