Small-scale operations on graphic sequences
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |