Matching Number

Author

Eric W. Weisstein
March 23, 2018

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

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

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

Counts

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Table[MatchingNumber/@Graphs[n],{n,9}]))//Column

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

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Get/@FileNames[]))//Column

A286951

Flatten[tallies]

tallies[[All,-1]]

A000088

Total/@tallies

Not in OEIS:

Total/@values

Missing

DateString[]

Grid[missing=Cases[Sort[GraphData[#,{"V","MatchingNumber","#"}]&/@GraphData[All]],{v_,_Missing,g_}:>{v,g}],Alignment->Left,Dividers->All]

Length[missing]

If[missing=!={},Export["/Users/eww/Documents/Mathematica/Paclets/GraphData/Data/ForPratt/MatchingNumber.tsv",{GraphNameToPrattName[#2],#1,GraphData[#2,"M"]}&@@@missing]]

Parametrized families

Andrasfai

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

FindSequenceFunction[seq,n]//FullSimplify

Antiprism

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

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

Apollonian

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

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

Bishop m×n

Table[GraphData[{"Bishop",{m,n}},"MatchingNumber"],{n,10},{m,n}]//Column

Table[If[Min[m,n]==1,0,2Floor[m n/4]],{n,10},{m,n}]//Column

Bishop n×n

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

BlackBishop n×n

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

FindSequenceFunction[seq,n]

Book

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

FindSequenceFunction[seq,n]//FullSimplify

Centipede

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

FindSequenceFunction[seq,n]

CocktailParty

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

FindSequenceFunction[Rest@DeleteMissing@seq,n-1]

Complete

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

FindSequenceFunction[seq,n-2]//FullSimplify

CompleteBipartite m×n

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

CompleteBipartite n×n

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

CompleteTripartite k×m×n

seq=Flatten[Table[{{k,m,n},GraphData[{"CompleteTripartite",{k,m,n}},"MatchingNumber"],XXX},{n,10},{m,n},{k,m}],2]

CompleteTripartite n×n×n

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

FindSequenceFunction[seq,n]//FullSimplify

Crown

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

FindSequenceFunction[seq,n-2]//Factor

CubeConnectedCycle

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

A001787

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

Table[n 2^(n-1),{n,3,8}]

Cycle

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

FindSequenceFunction[seq,n-2]//FullSimplify

DiagonalIntersection

A300531

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

Length/@l[[All,2,2]]

Conjecturally, a matching exists for every n with at most one unmatched vertex. This would imply a(n) = floor(A007569(n)/2). A computer search, using a simple nonbacktracking algorithm, has shown the existence of such matchings up to n = 22 and indeed for small n there are large numbers of maximum matchings (A292921). Such a matching could also be constructed from a Hamiltonian path (A300551) by selecting every other edge, so a proof that these graphs are Hamiltonian would also suffice. - _Andrew Howroyd_, Mar 12 2018

Empty

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

FibonacciCube

A004695

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

Table[MatchingNumber[FibonacciCubeGraph[n]],{n,10}]//Timing

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

Table[Fibonacci[n]/2-(1-Cos[2Pi n/3])/3,{n,0,20}]

seq=Table[Floor[Fibonacci[n+2]/2],{n,20}]

Floor[Fibonacci[Range[0,20]]/2]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{1,1,1,-1,-1},{1,1,2,4,6},20]

FoldedCube

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

FindSequenceFunction[seq,n-1]

Gear

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

FindSequenceFunction[seq,n-2]

Grid m×n

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

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

Grid n×n

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

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

Floor[((Range[10])^2)/2]

Grid k×m×n

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

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

Grid n×n×n

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

seq=Table[GraphData[{"Grid",{n,n,n}},"MatchingNumber"],{n,7}]

HalvedCube

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

FindSequenceFunction[Rest@seq,n-1]

Hanoi

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

FindSequenceFunction[seq,n]

Helm

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

FindSequenceFunction[seq,n-2]//FullSimplify

Hypercube

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

Table[(2^(n-1)),{n,10}]

FindSequenceFunction[Rest@seq,n]

King n×n

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

FindSequenceFunction[seq,n]//FullSimplify

Knight m×n

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

Knight n×n

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

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

FindSequenceFunction[seq,n]//FullSimplify

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

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

Mycielski

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

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

FindSequenceFunction[Rest@seq,n-1]

Odd

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

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

(seq=Table[MatchingNumber[OddGraph1[n]],{n,7}])//Timing

(seq=Table[MatchingNumber[OddGraph1[n]],{n,8}])//Timing

FindSequenceFunction[Rest@seq,n-1]

FindGeneratingFunction[seq,x]

Pan

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

FindSequenceFunction[seq,n-2]//FullSimplify

Table[Ceiling[n/2],{n,3,20}]

Path

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

FindSequenceFunction[seq,n]//FullSimplify

Prism

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

Queen m×n

Block[{m,n},DeleteCases[{#,GraphData[#,"MatchingNumber"],{m,n}=("Queen"/.GraphData[#,"NotationRules"]);Piecewise[{{0,m==n==1}},Floor[m n/2]]}&/@GraphData["Queen"],{_,x_,x_}]]

Queen n×n

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

FindSequenceFunction[seq,n]//FullSimplify

Rook m×n

Block[{m,n},DeleteCases[{#,GraphData[#,"MatchingNumber"],{m,n}=("Rook"/.GraphData[#,"NotationRules"]);Piecewise[{{0,m==n==1}},Floor[m n/2]]}&/@GraphData["Rook"],{_,x_,x_}]]

Rook n×n

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

FindSequenceFunction[seq,n]//FullSimplify

RookComplement n×n

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

FindSequenceFunction[seq,n]//FullSimplify

SierpinskiCarpet

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

FindSequenceFunction[seq,n]

SierpinskiSieve

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

FindSequenceFunction[seq,n]

Table[(2+(-1)^n+3^n)/4,{n,5}]

SierpinskiTetrahedron

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

FindSequenceFunction[seq,n]//FullSimplify

Star

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

Sun

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

Sunlet

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

FindSequenceFunction[seq,n-2]

Tetrahedral

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

(seq=Table[MatchingNumber[TetrahedralGraph[n]],{n,6,15}])//Timing

FindSequenceFunction[seq,n-5]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Transposition

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

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

Triangular

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

FindSequenceFunction[seq,n-4]

seq

TriangularGrid

A011848

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

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

Table[Floor[Binomial[n+2,2]/2],{n,0,10}]

TriangularHoneycombAcuteKnight

A289143

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

FindSequenceFunction[DeleteMissing@Drop[seq,3],n-3]

Table[Piecewise[{{3,n==4},{12,n==7}},(3 (n^2+n-3)+5 Cos[n Pi/2]+4 (-1)^n (Cos[n Pi/3]+Sqrt[3] Sin[n Pi/3]) (Cos[n Pi/2]-Sin[n Pi/2])-5 Sin[n Pi/2])/12],{n,20}]

TriangularHoneycombBishop

A011848

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

FindSequenceFunction[seq,n]

Table[Floor[Binomial[n+1,2]/2],{n,20}]

Do[Print[{n,MatchingNumber[TriangularHoneycombBishopGraph[n]]//Timing}],{n,20}]

TriangularHoneycombObtuseKnight

A011848 for n > 7

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

Table[MatchingNumber[TriangularHoneycombObtuseKnightGraph[n]],{n,30}]//Timing

gf=x FindGeneratingFunction[seq,x]

Simplify[gf]

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

Table[Piecewise[{{0,n<4},{3,n==4},{13,n==7}},Floor[Binomial[n+1,2]/2]],{n,30}]

TriangularHoneycombQueen

A011848

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

FindSequenceFunction[seq,n]

Table[Floor[Binomial[n+1,2]/2],{n,20}]

Do[Print[{n,MatchingNumber[TriangularHoneycombQueenGraph[n]]//Timing}],{n,20}]

TriangularHoneycombRook

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

FullSimplify[FindSequenceFunction[Rest@seq,n-1],n∈Integers]

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

Web

A032766

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

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

Wheel

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

FindSequenceFunction[seq,n-2]//FullSimplify

WhiteBishop n×n

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

FindSequenceFunction[seq,n-1]