Small-scale operations on graphic sequences
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913168073162752 |
|---|---|
| author | Rusu, Irena |
| author_facet | Rusu, Irena |
| contents | A sequence D=(d1, d2, ..., dn) of positive integers is graphic if it is the degree sequence of a simple graph, called in this case a {\em realization} of D. In this paper, we introduce the operation of 2-reduction, that subtracts 1 from two integers of D such that the resulting sequence D' is graphic if and only if D is graphic. We show that 2-reductions allow us to simply generate all the realizations of D, to prove existing characterizations of graphic sequences, as well as to propose new characterizations that highlight connections between mathematical and algorithmic aspects of graphic sequences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_28280 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Small-scale operations on graphic sequences Rusu, Irena Combinatorics Discrete Mathematics 05C90, 05C85, 68R10 A sequence D=(d1, d2, ..., dn) of positive integers is graphic if it is the degree sequence of a simple graph, called in this case a {\em realization} of D. In this paper, we introduce the operation of 2-reduction, that subtracts 1 from two integers of D such that the resulting sequence D' is graphic if and only if D is graphic. We show that 2-reductions allow us to simply generate all the realizations of D, to prove existing characterizations of graphic sequences, as well as to propose new characterizations that highlight connections between mathematical and algorithmic aspects of graphic sequences. |
| title | Small-scale operations on graphic sequences |
| topic | Combinatorics Discrete Mathematics 05C90, 05C85, 68R10 |
| url | https://arxiv.org/abs/2605.28280 |