Sterboul-Deming Graphs: Characterizations

A graph is said to be a Sterboul–Deming graph if $KE(G)=\mathrm{\varnothing }$, that is, if every vertex of $G$ belongs to a posy or a flower (structures introduced by Sterboul, Deming, and Edmonds). These graphs can be regarded as the structural counterparts of König–Egerváry graphs. In this paper, we present several characterizations of Sterboul–Deming graphs. We first study the case of graphs with a perfect matching and with a unique perfect matching, providing a constructive algorithm to obtain the decomposition $(SD(G),KE(G))$. Then, we extend the analysis to the general case through the Gallai–Edmonds decomposition. In addition, we show that the class of Sterboul–Deming graphs is remarkably broad: it contains all graphs having a $\{C_n:n\text{ odd}\}$-factor, providing a simple structural criterion for identifying such graphs. These results establish new connections between classical decomposition theorems and the internal structure of non–König–Egerváry graphs.