On strongly \(k\)-extendable graphs (Q2747174)

It is known that a matching \(M\) in a graph \(G= G(V,E)\) is a subset of \(E(G)\) in which no two edges have a vertex in common. A vertex \(v\) is saturated by \(M\) if some edge of \(M\) is incident to \(v\) and a matching is called to be perfect if it saturates every vertex of the graph. Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. For a given positive integer \(k\), \(1\leq k\leq n-1\), the graph \(G\) is \(k\)-extendable if for every matching \(M\) of size \(k\) in \(G\), there exists a perfect matching in \(G\) containing all the edges of \(M\). For an integer \(k\), \(0\leq k\leq n-2\), \(G\) is said to be strongly \(k\)-extendable or simply \(k^*\)-extendable if for every pair of vertices \(u\) and \(v\) of \(G\), \(G-\{u, v\}\) is \(k\)-extendable.NEWLINENEWLINENEWLINEIn the present paper these graphs are characterized for any \(k\). At first known results on \(k\)-extendable graphs useful for the investigation of \(k^*\)-extendable graphs are summarized. Then basic properties are proved, among other things also two theorems which yield a necessary and sufficient condition for graphs to be \(k^*\)-extendable, for example, Theorem 3.6: If \(G\) is a graph on \(2n\) vertices and if \(0\leq k\leq n-2\), then \(G\) is \(k^*\)-extendable iff for every matching \(M\) in \(G\) of size \(t\) with \(0\leq t\leq k\), \(G- V(M)\) is \((k-t)^*\)-extendable.NEWLINENEWLINENEWLINEIn the last section of the paper a number of sufficient conditions are established and with the help of these results the author gets his main result: If \(G\) is a \((k+2)\)-extendable non-bipartite graph on \(2n\) vertices and if \(0\leq k\leq n-3\), then \(G\) is \(k^*\)-extendable. A converse of this theorem is not true.