Minimum Vertex Degree

Author

Eric W. Weisstein
May 10, 2019

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

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

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

Counts

Tally[Sort[#]]&/@(values=Table[Min[VertexDegree[#]]&/@Graphs[n],{n,7}])//Column

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

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Get/@FileNames["*.m","MinimumVertexDegree"]))//Column

A294217

Flatten[tallies]

tallies[[All,1]]

Rest[tallies][[All,2]]

Drop[tallies,2][[All,-3]]

Rest[tallies][[All,-2]]

Table[Floor[n/2],{n,2,10}]

tallies[[All,-1]]

A000088

Total/@tallies

tallies[[All,1]]

Length/@tallies

Not in OEIS:

Total/@values

Parametrized families

Andrasfai

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

Antiprism

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

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

Apollonian

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

FindSequenceFunction[seq,n]

Bishop n×n

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

BlackBishop n×n

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

Book

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

Bruhat

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

FindSequenceFunction[seq,n]

Centipede

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

CocktailParty

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

FindSequenceFunction[seq,n]

Complete

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

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

CompleteBipartite m×n

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

DeleteCases[Block[{m,n},Sort[{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"MinimumVertexDegree"],
Min[m,n]
}&/@GraphData["CompleteBipartite"]]],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

DeleteCases[Block[{k,m,n},Sort[{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],
GraphData[#,"MinimumVertexDegree"],
Min[k+m,k+n,m+n]
}&/@GraphData["CompleteTripartite"]]],{_,x_,x_}]

CompleteTripartite n×n×n

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

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

CrossedPrism

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

CubeConnectedCycle

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

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

Cycle

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

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

DiagonalIntersection

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

Dipyramid

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

Empty

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

seq=Table[GraphData[{"Empty",n},"MinimumVertexDegree"],{n,20}]

FibonacciCube

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

(seq=Table[Min[VertexDegree[FibonacciCubeGraph[n]]],{n,17}])//Timing

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

Table[Ceiling[n/3],{n,17}]

FoldedCube

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

Gear

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

Grid m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"MinimumVertexDegree"],
Piecewise[{{0,m==n==1},{1,Min[m,n]==1}},2]
},{n,10},{m,n}],1],{_,x_,x_}]

Table[Max[VertexDegree[GridGraph[{m,n}]]]-Piecewise[{{0,m==n==1},{1,m n==2},{2,Min[m,n]==1||m==n==2},{3,Min[m,n]==2}},4],{m,20},{n,20}]//Flatten//Union

Grid n×n

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

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

Grid k×m×n

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

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"MinimumVertexDegree"],
Piecewise[{
{0,k==m==n==1},
{1,k m n==Max[k,m,n]},
{2,Min[k,m,n]==1}
},3]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Table[Max[VertexDegree[GridGraph[{k,m,n}]]]-Piecewise[{
{0,k==m==n==1},
{1,k m n==2},
{2,k m n===Max[k,m,n]||(Min[k,m,n]Max[k,m,n]==2)},
{3,k m n==2Max[k,m,n]||k==m==n==2},
{4,Min[k,m,n]==1||(Min[k,m,n]==2&&k m n==4Max[k,m,n])},
{5,Min[k,m,n]==2}},6],{k,20},{m,20},{n,20}]//Flatten//Union

Grid n×n×n

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

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

HalvedCube

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

FindSequenceFunction[seq,n]

Hanoi

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

Helm

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

Hypercube

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

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

Keller

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

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

Table[4^n-3^n-n,{n,5}]

FindSequenceFunction[DeleteMissing@seq,n]

FindLinearRecurrence[DeleteMissing@seq]

FindGeneratingFunction[DeleteMissing@seq,x]

King m×n

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"MinimumVertexDegree"],
Piecewise[{{0,m==n==1},{1,Min[m,n]==1}},3]
},{n,10},{m,n}],1],{_,x_,x_}]

Table[Min[VertexDegree[GridGraph[{m,n}]]]-Piecewise[{{0,m==n==1},{1,m n==2},{2,Min[m,n]==1||m==n==2},{3,Min[m,n]==2}},4],{m,20},{n,20}]//Flatten//Union

King n×n

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

Knight m×n

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

Knight n×n

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

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

Ladder

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

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

LadderRung

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

MengerSponge

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

Table[Max[VertexDegree[MengerSpongeGraph[n]]],{n,4}]//Timing

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

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

Path

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

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

Prism

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

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

Queen m×n

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

Table[Min[VertexDegree[QueenGraph[m,n]]]-XXX,{m,20},{n,20}]//Flatten//Union

Queen n×n

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

FindSequenceFunction[seq,n]//FullSimplify

Rook n×n

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

RookComplement n×n

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

FindSequenceFunction[seq,n]

SierpinskiCarpet

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

SierpinskiSieve

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

SierpinskiTetrahedron

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

Star

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

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

Sun

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

Sunlet

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

Tetrahedral

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

TorusGrid n×n

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

Transposition

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

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

Triangular

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

FindSequenceFunction[seq,n-1]

TriangularGrid

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

Web

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

Wheel

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

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

WhiteBishop n×n

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