Splitters and barriers in open graphs having a perfect internal matching

Abstract

A counterpart of Tutte's Theorem and Berge's formula is proved for open graphs with perfect (maximum) internal matchings. Properties of barriers and factor-critical graphs are studied in the new context, and an efficient algorithm is given to find maximal barriers of graphs having a perfect internal matching.