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)\).