Unexpectedly, a Symmetry on Unlabeled Graphs
The Electronic Journal of Combinatorics · 2026-11-06 · 33 (4)
DOI: 10.37236/15312 ↗At a glance
Journal article in The Electronic Journal of Combinatorics, published online on 2026-11-06. Written by Florian Fürnsinn and 2 co-authors.
Abstract (original language)
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 simple connected graphs with 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.
Cite
APA
Fürnsinn, F., Gangl, M., & Rubey, M. (2026). Unexpectedly, a Symmetry on Unlabeled Graphs. The Electronic Journal of Combinatorics, 33(4). https://doi.org/10.37236/15312
Vancouver
Fürnsinn F, Gangl M, Rubey M. Unexpectedly, a Symmetry on Unlabeled Graphs. The Electronic Journal of Combinatorics. 2026;33(4). doi:10.37236/15312
BibTeX
@article{Frnsinn2026,
author = {Fürnsinn, Florian and Gangl, Moritz and Rubey, Martin},
title = {Unexpectedly, a Symmetry on Unlabeled Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {4},
doi = {10.37236/15312}
}
EUVIMED