Menu
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 been investigated only for the case \(k = 0\). In this paper, we focus on the problem of characterizing strongly \(k\)-extendable graphs for any \(k\). We present a number of properties of strongly \(k\)-extendable graphs including some necessary and sufficient conditions for strongly \(k\)-extendable graphs.