Generalized Sterboul--Deming Configurations

Abstract

Sterboul and Deming gave classical matching-based characterizations of non-Kőnig--Egerváry graphs through flower--posy and blossom-pair configurations. We consider two classical configuration families, denoted \(T\) and \(S\), and introduce a new walk-based family \(J\), based on \(J\)-flowers and \(J\)-posies. Our main result proves that, for every graph \(G\), \[ \SD_T(G)=\SD_S(G)=\SD_J(G). \] Thus the additional flexibility of the \(J\)-framework preserves the set of vertices detected by the classical configurations. The proof is vertex-preserving and passes through strict-Hall structure in traces of \(J\)-posies. As a consequence, every prescribed vertex of a connected matchable strict-Hall graph lies in a rigid \(T\)-posy for a suitable perfect matching, linking the theory naturally with matching-covered graphs.

27 pages, 3 figures