On a Minimum Cutset of Strongly $k$-Extendable Graphs

Abstract

Let G be a simple connected graph on 2n vertices with a perfect matching. For a positive integer k, $1\le \text{k}\le \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\le \text{k}\le \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}\ge 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.