Abstract: On (connected) unlabeled graphs, very few bijections of interest, apart from taking the graph complement, are known. In this talk I will present a symmetry on the set of unlabeled connected simple graphs, hinting at the existence of an involution on them. More precisely, I will show that the maximum number of degree one vertices connected to a single vertex in a graph and the maximum number of vertices sharing the same closed neighborhood (minus one) are jointly symmetrically distributed. This result generalizes works of Kilibarda and Gessel -- Li and the proof relies on the theory of species. The talk is based on ongoing joint work with M. Gangl and M. Rubey.
An Unexpected Symmetry on Graphs
26.11.2024 15:00 - 16:30
Organiser:
I. Fischer (U Wien), M. Schlosser (U Wien)
Location: