On Minimum Degree of Strongly \(k\)-Extendable Graphs

Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. For a positive integer \(k\), \(1 \leq k \leq n – 1\), \(G\) is \(k\)-\emph{extendable} if for every matching \(M\) of size \(k\) in \(G\), there is a perfect matching in \(G\) containing all the edges of \(M\). For an integer \(k\), \(0 \leq k \leq n – 2\), \(G\) is \emph{strongly \(k\)-extendable} if \(G\) – \(\{u, v\}\) is \(k\)-extendable for every pair of vertices \(u\) and \(v\) of \(G\). The problem that arises is that of characterizing \(k\)-extendable graphs and strongly \(k\)-extendable graphs. The first of these problems has been considered by several authors whilst the latter has only been recently studied by the author. In a recent paper, we established a number of properties of strongly \(k\)-extendable graphs including some sufficient conditions for strongly \(k\)-extendable graphs. In this paper, we focus on a necessary condition, in terms of minimum degree, for strongly \(k\)-extendable graphs. Further, we determine the set of realizable values for minimum degree of strongly \(k\)-extendable graphs. A complete characterization of strongly \(k\)-extendable graphs on \(2n\) vertices for \(k = n – 2\) and \(n – 3\) is also established.