Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 54 min ago
Peer-reviewedCC BY 4.0The Electronic Journal of Combinatorics

Unexpectedly, a Symmetry on Unlabeled Graphs

  • Florian Fürnsinn
  • Moritz Gangl
  • Martin Rubey
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Exact counting of unlabeled quartic graphs by permutation-cycle aggregation
    Yue Cheng, Zhipeng Xu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Premaniplexes of rank $3$ and $4$ as symmetry type graphs of maniplexes
    Maruša Lekše
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Reconstruction and Symmetry of Two-Token Graphs
    Yuanming Luo, Hao Hu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold
    Zejia Chen, Chunyang Wang, Xinyuan Zhang
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv
  5. Importance Weighting for Unlabeled-unlabeled Learning under Distribution Shift
    Atsutoshi Kumagai, Tomoharu Iwata, Hiroshi Takahashi +3
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@article{furnsinn2026unexpectedly,
  title = {{Unexpectedly, a Symmetry on Unlabeled Graphs}},
  author = {Florian Fürnsinn and Moritz Gangl and Martin Rubey},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  month = nov,
  doi = {10.37236/15312},
  url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p32},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - Unexpectedly, a Symmetry on Unlabeled Graphs
AU  - Florian Fürnsinn
AU  - Moritz Gangl
AU  - Martin Rubey
PY  - 2026
DA  - 2026/11/06
JO  - The Electronic Journal of Combinatorics
DO  - 10.37236/15312
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p32
AB  - 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.
SN  - 1077-8926
ER  -