Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.03665 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909602720776192 |
|---|---|
| author | Fürnsinn, Florian Gangl, Moritz Rubey, Martin |
| author_facet | Fürnsinn, Florian Gangl, Moritz Rubey, Martin |
| contents | We exhibit the joint symmetric distribution of the following two parameters on the set of unlabeled, simple, connected graphs with $n$ vertices. The first parameter is the maximal number of leaves attached to a vertex. The second parameter is the size of the largest set of vertices sharing the same closed neighborhood minus $1$.
Apparently, this is the first example of a natural, non-trivial equidistribution of graph parameters on unlabeled connected graphs on a fixed set of vertices.
Our proof is enumerative, using the theory of species. Exhibiting an explicit bijection interchanging the two parameters remains an open problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_03665 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unexpectedly, a symmetry on unlabeled graphs Fürnsinn, Florian Gangl, Moritz Rubey, Martin Combinatorics We exhibit the joint symmetric distribution of the following two parameters on the set of unlabeled, simple, connected graphs with $n$ vertices. The first parameter is the maximal number of leaves attached to a vertex. The second parameter is the size of the largest set of vertices sharing the same closed neighborhood minus $1$. Apparently, this is the first example of a natural, non-trivial equidistribution of graph parameters on unlabeled connected graphs on a fixed set of vertices. Our proof is enumerative, using the theory of species. Exhibiting an explicit bijection interchanging the two parameters remains an open problem. |
| title | Unexpectedly, a symmetry on unlabeled graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.03665 |