Counting graphs admitting a strictly matched involution

@misc{andres2026counting,
  title = {{Counting graphs admitting a strictly matched involution}},
  author = {Stephan Dominique Andres and Igor Režan},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06703},
  eprint = {2611.06703},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06703},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Counting graphs admitting a strictly matched involution
AU  - Stephan Dominique Andres
AU  - Igor Režan
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06703
UR  - https://arxiv.org/abs/2611.06703
AB  - We study graphs admitting a strictly matched involution, i.e., graphs for which a strictly matched involution exists. A strictly matched involution of a graph G is a self-inverse graph automorphism f with the properties that the fixed point set of f induces a complete subgraph in G and, for the vertices that are no fixed points, every vertex is connected to its image under f by an edge. Andres, Huggan, Mc Inerney, and Nowakowski (2019) determined upper and lower bounds for the number A(n) of graphs admitting a strictly matched involution on n vertices. We improve the upper bound and we compute the exact values for the number A(n) for all n≤11. Furthermore, we use combinatorial enumeration techniques and a decomposition lemma to determine the number C(n,m) of graphs admitting a strictly matched involution with n vertices and m edges for several infinite classes of pairs (n,m).
ER  -