2025/05/06 by Florian Fürnsinn, Fürnsinn, Florian, Moritz Gangl +3
Computer Science · #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2505.03665
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.