Sterboul-Deming Graphs: Characterizations

Abstract

A graph is said to be a Sterboul--Deming graph if $KE(G)=\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.