To Determine $1$-Extendable Graphs and its Algorithm

Abstract

Let $G$ be a graph with a perfect matching $M_0$. It is proved that $G$ is $1$-extendable if and only if for any pair of vertices $x$ and $y$ with an $M_0$-alternating path $P_y$ of length three which starts with an edge that belongs to $M_0$, there exists an $M_0$-alternating path $P$ connecting $x$ and $y$, of which the starting and the ending edges do not belong to $M_0$. With this theorem, we develop a polynomial algorithm that determines whether the input graph $G$ is $1$-extendable, the time complexity of the algorithm is $O(|E{|}^2)$.