Generalized Sterboul--Deming Configurations

Source 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.