On a Minimum Cutset 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 \text{k} \leq \text{n}-1\), G is \(k\)-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 \text{k} \leq \text{n} – 2\), G is trongly \(k\)-extendable if \(\text{G} – \{\text{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 while the latter has been recently investigated. In this paper, we focus on a minimum cutset of strongly k-extendable graphs. For a minimum cutset S of a strongly k-extendable graph G, we establish that if \(|\text{S}| = \text{k + t}\), for an integer \(\text{t} \geq 3\), then the independence number of the induced subgraph G[S] is at most \(2\) or at least k + 5 – t. Further, we present an upper bound on the number of components of G – S.