Successive vertex orderings of connected graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908948064370688 |
|---|---|
| author | Agrawal, Prarthana Erturk, Abdurrahman Hadi Louis, Ard |
| author_facet | Agrawal, Prarthana Erturk, Abdurrahman Hadi Louis, Ard |
| contents | A successive vertex ordering of a graph is a linear ordering of its vertices in which every vertex except the first has at least one neighbour appearing earlier. Such orderings arise naturally in incremental growth and connectivity-preserving constructions, where vertices are added sequentially and must attach to the existing structure. We derive an exact formula for the number of successive vertex orderings of any finite connected graph. The formula is obtained via an inclusion--exclusion argument over independent sets and depends on two explicit combinatorial parameters, one of which is defined recursively. The result applies to all finite connected graphs without requiring regularity or symmetry assumptions. We also express the enumeration as a weighted generating polynomial over independent sets; its value at $x = -1$ recovers the total count of successive orderings, and the $k$-th derivative at this point encodes the number of orderings in which exactly $k$ vertices have no earlier neighbour. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_07408 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Successive vertex orderings of connected graphs Agrawal, Prarthana Erturk, Abdurrahman Hadi Louis, Ard Combinatorics 05C30, 05A15, 05C31, 05C69 A successive vertex ordering of a graph is a linear ordering of its vertices in which every vertex except the first has at least one neighbour appearing earlier. Such orderings arise naturally in incremental growth and connectivity-preserving constructions, where vertices are added sequentially and must attach to the existing structure. We derive an exact formula for the number of successive vertex orderings of any finite connected graph. The formula is obtained via an inclusion--exclusion argument over independent sets and depends on two explicit combinatorial parameters, one of which is defined recursively. The result applies to all finite connected graphs without requiring regularity or symmetry assumptions. We also express the enumeration as a weighted generating polynomial over independent sets; its value at $x = -1$ recovers the total count of successive orderings, and the $k$-th derivative at this point encodes the number of orderings in which exactly $k$ vertices have no earlier neighbour. |
| title | Successive vertex orderings of connected graphs |
| topic | Combinatorics 05C30, 05A15, 05C31, 05C69 |
| url | https://arxiv.org/abs/2604.07408 |