A300531 - OEIS

%I #17 Mar 13 2018 05:48:47

%S 1,2,5,9,21,28,67,85,170,156,364,385,690,696,1198,927,1947,1930,3003,

%T 2981

%N Matching number of the n-polygon diagonal intersection graph.

%C 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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MatchingNumber.html">Matching Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PolygonDiagonalIntersectionGraph.html">Polygon Diagonal Intersection Graph</a>

%Y Cf. A007569, A291947, A292921, A300550, A300551.

%K nonn,more

%O 3,2

%A _Eric W. Weisstein_, Mar 08 2018

%E a(21)-a(22) from _Andrew Howroyd_, Mar 12 2018