Sterboul-Deming Graphs: Characterizations
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908877096747008 |
|---|---|
| author | Pereyra, Kevin |
| author_facet | Pereyra, Kevin |
| contents | A graph is said to be a Sterboul--Deming graph if $KE(G)=\emptyset$, 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 \textnormal{ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09796 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sterboul-Deming Graphs: Characterizations Pereyra, Kevin Combinatorics A graph is said to be a Sterboul--Deming graph if $KE(G)=\emptyset$, 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 \textnormal{ 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. |
| title | Sterboul-Deming Graphs: Characterizations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.09796 |