Matching extension and the genus of a graph (Q1107545): Difference between revisions

A connected graph G of order p and having a perfect matching (a spanning, 1-regular subgraph) is said to be n-extendable (where n is a positive integer, with \(n\leq (p-2)/2)\) if every matching in G of size n is a subset of a perfect matching. The main result of the present paper is: If G is any connected graph, with genus \(\gamma >0\), then (a) G is not \((\lfloor 9/2+18(\gamma -1)/(7+\sqrt{48\gamma -47})\rfloor)\)-extendable; (b) if, in addition, G has no 3-cycles, then G is not \((2+\lfloor 2\sqrt{\gamma})\)-extendable.