The Lorenz order in graph theory: A new proof and extension of the theorems of Hakimi and of Havel-Hakimi
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910773027012608 |
|---|---|
| author | Egghe, Leo |
| author_facet | Egghe, Leo |
| contents | This paper studies the relation between the Lorenz majorization order and the realizability of degree sequences X of a network in the sense of being graphical or connected graphical (c-graphical) or not. We prove the main result that, if X is dominated (in the Lorenz majorization sense) by X' and X' is (c-) graphical, the X is also (c-) graphical. We present a simple proof and a generalization of the Havel-Hakimi theorem, using the Lorenz order formalism. From this, a classical result of Hakimi on trees follows but also a new generalization to general connected networks. From this, a characterization of c-graphical sequences in terms of the Lorenz majorization order is given. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_02937 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Lorenz order in graph theory: A new proof and extension of the theorems of Hakimi and of Havel-Hakimi Egghe, Leo General Mathematics 05C07 This paper studies the relation between the Lorenz majorization order and the realizability of degree sequences X of a network in the sense of being graphical or connected graphical (c-graphical) or not. We prove the main result that, if X is dominated (in the Lorenz majorization sense) by X' and X' is (c-) graphical, the X is also (c-) graphical. We present a simple proof and a generalization of the Havel-Hakimi theorem, using the Lorenz order formalism. From this, a classical result of Hakimi on trees follows but also a new generalization to general connected networks. From this, a characterization of c-graphical sequences in terms of the Lorenz majorization order is given. |
| title | The Lorenz order in graph theory: A new proof and extension of the theorems of Hakimi and of Havel-Hakimi |
| topic | General Mathematics 05C07 |
| url | https://arxiv.org/abs/2409.02937 |