A333348 Matching number of the tree of n vertices with the largest number of maximum matchings.

0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 24, 24, 24

Offset: 0

Author

Kevin Ryde, Mar 15 2020

Keywords

• nonn

Comments

Heuberger and Wagner consider how many different maximum matchings a tree of n vertices may have. They determine the unique tree (free tree) of n vertices with the largest number of maximum matchings, or at n=6 and n=34 the two trees with equal largest number. a(n) is the matching number of the unique tree, and of both n=34 trees since they have the same matching number. For n=6, a(6)=1 is the star-6 which is their T_{6,1}. The other n=6 is their T_{6,2} and its matching number would be a(6)=2 instead.

The trees n!=2 have all pairs of leaves an even distance apart (the type of free tree counted by A304867). Vertices an even distance to a leaf are Heuberger and Wagner's type A, and vertices an odd distance to a leaf are type B. Per their definitions (and for any "even distance leaves" tree in fact), all type B vertices must be matched in a maximum matching and consequently the matching number is the number of type B vertices. 2n/7 appears in the formula below since each "C" part contains 7 vertices of which 2 are type B; then there are certain fixed additional B vertices according to n mod 7.

Links

• Paolo Xausa, Table of n, a(n) for n = 0..10000
• Clemens Heuberger and Stephan Wagner, The Number of Maximum Matchings in a Tree, Discrete Mathematics, volume 311, issue 21, November 2011, pages 2512-2542; arXiv preprint, arXiv:1011.6554 [math.CO], 2010.
• Clemens Heuberger and Stephan Wagner, Number of Maximum Matchings In a Tree - Sage Worksheet, constructing the trees.
• Kevin Ryde, vpar examples/most-maximum-matchings.gp creating, counting, and recurrences, in PARI/GP.
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,1,-1).

Crossrefs

Cf. A333347 (number of maximum matchings).

Programs

Mathematica

A333348[n_] := Switch[n, 2, 1, 6, 1, 13, 3, 20, 5, _, Floor[(2*n + 2)/7]];
Array[A333348, 100, 0] (* Paolo Xausa, Jun 18 2024 *)

Formula

a(2)=a(6)=1, a(13)=3, a(20)=5, and otherwise a(n) = floor((2n+2)/7).