Counting graphs admitting a strictly matched involution

arXiv:2611.06703 · math.CO · Submitted 2026-11-04 · Read on arXiv

math.CO

Submitted: 2026-11-04

Updated: 2026-11-04

Comments: 27 pages, 5 figures

License: http://creativecommons.org/licenses/by/4.0/

The gist: We study graphs admitting a strictly matched involution, i.e., graphs for which a strictly matched involution exists.

Terminology

Abstract

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 at most11. 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).

Related papers