Counting graphs admitting a strictly matched involution
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality