On $(n-2)$-Extendable Graphs

Abstract

Let $G$ be a simple connected graph on $2n$ vertices with a perfect matching. $G$ is $k$-$extendable$ if for any set $M$ of $k$ independent edges, there exists a perfect matching in $G$ containing all the edges of $M$. $G$ is $minimallyk-extendable$ if $G$ is $k$-extendable but $G–uv$ is not $k$-extendable for every pair of adjacent vertices $u$ and $v$ of $G$. The problem that arises is that of characterizing $k$-extendable and minimally $k$-extendable graphs. The first of these problems has been considered by several authors whilst the latter has only been recently studied. In a recent paper, we established several properties of minimally $k$-extendable graphs as well as a complete characterization of minimally $(n–1)$-extendable graphs on $2n$ vertices. In this paper, we focus on characterizing minimally $(n–2)$-extendable graphs. A complete characterization of $(n–2)$-extendable and minimally $(n–2)$-extendable graphs on $2n$ vertices is established.