WorksMathematics
Counting graphs admitting a strictly matched involution
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 is a self-inverse graph automorphism with the properties that the fixed point set of induces a complete subgraph in and, for the vertices that are no fixed points, every vertex is connected to its image under by an edge. Andres, Huggan, Mc Inerney, and Nowakowski (2019) determined upper and lower bounds for the number of graphs admitting a strictly matched involution on vertices. We improve the upper bound and we compute the exact values for the number for all . Furthermore, we use combinatorial enumeration techniques and a decomposition lemma to determine the number of graphs admitting a strictly matched involution with vertices and edges for several infinite classes of pairs .
Introduction
Let be a (simple finite) graph. A graph automorphism of is a bijective map with the property that, for every two vertices , the vertices and are connected by an edge if, and only if, the vertices and are connected by an edge. An involution of is a graph automorphism with for every vertex . By an involution of , the vertex set of is separated into two subsets: the set
of fixed points and the set
of points of orbit 2. An involution of is called strictly matched if
and
induces a clique, i.e., a graph in which every two vertices are connected by an edge.
Then, an edge of type is called a matching edge of the pair . A graph admitting a strictly matched involution is a graph for which a strictly matched involution exists.
Python3 enumeration program
ISSN subm. to DMTCS © 2026 by the author(s) Distributed under a Creative Commons Attribution 4.0 International License
Andres et al. [3] introduced graphs admitting a strictly matched involution, motivated by a specific game, the orthogonal colouring game. In this context, they proved that, if graphs admitting a strictly matched involution are the boards of the orthogonal colouring game, then the second player always has a strategy to force a draw [3 Thm 1]. The orthogonal colouring game is a representative of a large class of games, the so-called scoring games, which recently have received considerable attention in game theory by several authors, e.g., by Seo and Slater [21], Johnson [10], Larsson et al. [11], Larsson et al. [12], Larsson et al. [13], Larsson et al. [14], Stewarts [22], Rai et al. [19], Davies et al. [8], or Larsson et al. [15]. Graphs admitting a strictly matched involution are also interesting from a computational perspective: Andres et al. [5] established the NP-completeness of the decision problem to recognise whether a graph admits a strictly matched involution.
In the present paper, we focus on counting (the isomorphism classes of) graphs admitting a strictly involution with vertices and edges for . Moreover, for , let
denote the number of graphs admitting a strictly matched involution with vertices,
denote the number of graphs admitting a strictly matched involution with edges, and
denote the number of graphs admitting a strictly matched involution with vertices and edges,
respectively, up to isomorphism. We aim to obtain partial answers to the following problems.
Problem 1.1 Given as input, determine .
Problem 1.2 Given as input, determine .
Problem 1.3 Given as input, determine .
As main results we determine the exact values for several infinite classes of pairs . Furthermore, we improve a general upper bound given by Andres et al. (2019) for the numbers . Finally, we implement a computer program that determines and for .
The structure of the paper is as follows. After fixing some notation in § 2.1.1 and a discussion of previous results related to this paper in § 2.1.2 and § 2.1.3, in § 2.2 we list our main results. § 3 contains the proof of the new upper bound (Theorem 3.1). In § 4 we present the results of the computer program. § 5 and § 6 are devoted to the proofs of our mathematical main results (Observation 3.2, Theorem 3.3, and Theorem 3.4). We conclude with some open problems in § 7. The idea and the source code of the program are displayed in Appendix § 8.
Preliminaries
Notation
Let denote the set of nonnegative integers. For , let denote the set of all subsets of with exactly elements. A graph is a pair consisting of a finite set , the set of vertices, and a set , the set of edges. By this definition, all graphs in this paper are assumed to be simple and finite. Edges are usually written as . Two graphs and are isomorphic if there is a bijective map satisfying
Such a map is called a graph isomorphism from to . Following standard graph theory conventions, isomorphic graphs are considered as the same objects. A graph automorphism of is a graph isomorphism from to .
For , let denote the clique (or also called complete graph) on vertices, i.e.,
with . Some special graphs admitting a strictly matched involution with 4 vertices are the 4-cycle, denoted by , and the paw (sometimes also called 3-pan), which is denoted by in this paper, see Figure 1. The disjoint union of two graphs and , i.e., a graph for an isomorphic copy of and an isomorphic copy of with , is denoted by ; and, for , the -fold disjoint union is defined recursively by and for . The complete join of two graphs and , i.e., the graph that is generated from the disjoint union by connecting every vertex of the copy of with every vertex of the copy of , is denoted by . For a graph , let denote the complement of , and, if , then is the graph . If , then is the subgraph of induced by , i.e., the graph obtained from by deleting the vertex and all edges containing . The degree of a vertex in is the number of the edges containing .

Figure 1. The graphs admitting a strictly matched involution with 4 vertices
The structure of graphs admitting a strictly matched involution
Our analysis is based on the following result of Andres et al. (2019), which describes the structure of graphs admitting a strictly matched involution.
Theorem 2.1 (Andres et al. (2019), Cor 9) Every graph on vertices admitting a strictly matched involution has a partition of its vertex set into three (possibly empty) vertex subsets inducing a clique of size and two isomorphic graphs and , each of size , for some with , respectively. Moreover, there is a graph isomorphism such that
(1) for every pair of vertices and with and every vertex , either both or none of and are edges in ;
(2) for every pair of vertices and with , we have ;
(3) for every two pairs and of vertices with and , , and , either both or none of and are edges in .
We remark that the graph isomorphism between the subgraphs and in Theorem 2.1 can be extended to a strictly matched involution of the whole graph by defining
As illustrated in Figure 2, by Theorem 2.1, the edge set of a graph admitting a strictly matched involution can be decomposed into
Figure 2. Structure of graphs admitting a strictly matched involution according to Theorem 2.1 and the five different types of edges of such a graph with regard to . The edges of type (1), (2), and (3) refer to (1), (2), and (3) in Theorem 2.1.
pairs of clique-connecting edges, i.e., edges implied by Theorem 2.1 (1);
matching edges (cf. Theorem 2.1 (2));
pairs of cross edges, i.e., the edges implied by Theorem 2.1 (3);
pairs of subgraph edges, i.e., the edges of and ; and
clique edges, i.e., the edges induced by .
However, there might be many ways of such a decomposition, depending on the choice of , , and the matching edges. For example, in the worst case, i.e., if is the complete graph on vertices, there are
ways to obtain such a decomposition of the vertex set of together with a graph isomorphism as
is the number of ways to choose vertices for the clique ,
is the number of perfect matchings in a , and
there are ways in total to choose which vertex of a matching edge belongs to .
We remark that the numbers constitute the sequence A047974 in The On-Line Encyclopedia of Integer Sequences (OEIS Foundation Inc. (2026)).
The numbers of this sequence occur in many different mathematical domains and applications, e.g., in a certain model of ad hoc mobile networks described by Latouche and Taylor [16], in the theory of operator algebras used in mathematical physics (cf. Amdeberhan et al. [2]), as numbers of palindromic assembly words (i.e., double occurrence words that are in a certain way isomorphic to its inverse word), which were investigated by Burns et al. [7] in the context of DNA recombination, as total numbers of symmetric diagrammes in a Breuer algebra in the theory of diagram algebras (cf. Halverson and Reeks [9]), or as numbers of posets on elements the components of which consist of at most 2 elements (cf. Aljohani et al. [1]). Furthermore, Bala [6] remarked a nice property of the sequence A047974: for any , it is -periodic modulo . Some more general and more complicated counting sequences that are related to the sequence A047974 are given, e.g., by Quaintance and Kwong [18].
We consider counting graphs admitting a strictly matched involution, which is another, more complicated way of counting related to the sequence A047974: starting with the decompositions of the complete graph with respect to a graph isomorphism from to (which are the objects counted by the sequence A047974), for each way of deleting pairs of clique-connecting edges, subgraph edges, and/or cross edges, we obtain a graph admitting a strictly matched involution and, by Theorem 2.1, we obtain every graph admitting a strictly matched involution on vertices by this procedure. However, at this moment, we have constructed many isomorphic graphs. In order to count them, we have to group them into isomorphism classes. As graphs admitting a strictly matched involution can be derived in this very natural way from the combinatorial structures defining the sequence A047974, which is of significant interest in many mathematical domains, the study of graphs admitting a strictly matched involution (besides its importance in game theory) might turn out to be of general interest, too.
Counting graphs admitting a strictly matched involution
For the number of (isomorphism classes of) graphs admitting a strictly matched involution with vertices, i.e., the entries of the sequence A363771 in the OEIS (OEIS Foundation Inc. (2026)), the following lower and upper bounds (with a large gap inbetween) are known. The bounds depend on the number of all (isomorphism classes of) graphs with vertices, i.e., the entries of the sequence A000088 in the OEIS (OEIS Foundation Inc. (2026)).
Theorem 2.2 (Andres et al. [4], Thm 2) For every ,
Theorem 2.3 (Andres et al. (2019), Thm 11) For every ,
Our counting results
The first result of the present paper is the following improvement of Theorem 2.3.
Theorem 3.1 For every ,
Moreover, we use the construction of Theorem 3.1 to develop a computer program that enumerates and counts the number of (isomorphism classes of) graphs admitting a strictly matched involution with vertices and edges. Thereby, we obtain all values of with . Furthermore, we determine the following exact values for for some pairs , as given in Observation 3.2, Theorem 3.3, and Theorem 3.4.
Observation 3.2 Let . Then
(a) if ;
(b) if ;
(c) if and ;
(d) if and .
Theorem 3.3 Let . Then
(a) if ;
(b) if and ;
(c) if , , and ;
(d) if , , and .
Theorem 3.4 Let . Then
(a) if ;
(b) if and ;
(c) if and .
Using the results of Observation 3.2 and Theorem 3.3 and the results of the computer program, we are able to determine the number of (isomorphism classes of) graphs admitting a strictly matched involution with edges, i.e., the entries of the sequence A363772 in the OEIS (OEIS Foundation Inc. (2026))) for .
Proof of the improved upper bound
Proof of Theorem 3.1. Let be a graph admitting a strictly matched involution with vertices. By Theorem 2.1, the vertex set of can be partitioned in two subsets and , each of cardinality for some with , and a subset of cardinality such that induces a complete graph and and induce two isomorphic graphs and . By property (2) in Theorem 2.1, vertices that are mapped to each other by the isomorphism are connected by matching edges. We have the following choices.
We have many possibilities to choose the edges in .
For each of the unordered pairs of pairs and of corresponding matched vertices and , by property (3) in Theorem 2.1, we have two choices: either the crossing edges and are both in or none of them; this gives us choices.
By property (1) in Theorem 2.1, each of the vertices in the clique is adjacent to each vertex of one of the subsets of the partition . Since the vertices of the clique are indistinguishable, this is equivalent to putting indistinguishable balls in numbered cases (possibly several balls in a case). Thus we get as many choices as the number of -combinations of with repetition, which is
As the three choices are independent, we get in total
ways to choose the edges for fixed , and summing over all possible gives the upper bound for in the theorem.
In the proof of Theorem 2.3, Andres et al. (2019) basically used the same idea as in the above proof of Theorem 3.1, but they assumed that the vertices of the cliques are distinguishable, which gives us the number of -variations of (for and )
instead of the number of -combinations of . As the number of -variations of is an upper bound for the number of -combinations of we have
thus the new upper bound from Theorem 3.1 is better than the old upper bound from Theorem 2.3.
Exact values: computational results
Režan [20] computed the values of for . Theorem 3.1 gives an improved idea how to enumerate the graphs admitting a strictly matched involution on vertices by computer: we construct all configurations that are counted in the upper bound of Theorem 3.1 and then make isomorphism tests to exclude isomorphic copies. The program based on the improved idea is displayed in Appendix A.2.
By this approach, we compute the exact values of the sequence for all in the range , thus, being able to deal with the case , too. The running time for on a standard laptop was in 38 seconds, the case needed 27 minutes, and the case more than 31 hours.
We implemented the values in the OEIS (OEIS Foundation Inc. (2026)) in sequence A363771. In Table 1 we list those values together with the values for the lower bound from Theorem 2.2 and the upper bounds from Theorem 3.1 and Theorem 2.3. We remark that the slight improvement given in Theorem 3.1 is significant for large . However, there are still large significant gaps between the lower and new upper bound and the exact values of for large . Thus further improvements of the bounds might be an interesting topic of further research.
Moreover, with the program we indeed determined the values for for all and . The results are displayed in Table 2.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 2 | 2 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 2 | 2 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 6 | 1 | 3 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 5 | 5 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 0 | 0 |
| 8 | 2 | 0 | 0 | 7 | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 9 | 0 | 6 | 11 | 0 | 0 | 7 | 6 | 0 | 0 | 0 | 0 | 0 |
| 10 | 1 | 0 | 0 | 16 | 17 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 11 | 4 | 13 | 0 | 0 | 21 | 19 | 0 | 0 | 0 | 0 | 0 | 0 |
| 12 | 0 | 0 | 30 | 40 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 13 | 2 | 14 | 0 | 0 | 62 | 57 | 0 | 0 | 0 | 0 | 0 | 0 |
| 14 | 0 | 0 | 41 | 74 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 15 | 1 | 11 | 0 | 0 | 140 | 155 | 0 | 0 | 0 | 0 | 0 | 0 |
| 16 | 0 | 50 | 128 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 17 | 5 | 0 | 0 | 292 | 383 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 18 | 0 | 40 | 175 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 19 | 2 | 0 | 0 | 510 | 870 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 20 | 0 | 28 | 199 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 21 | 1 | 0 | 0 | 775 | 1745 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 22 | 16 | 184 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 23 | 0 | 0 | 987 | 3090 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 24 | 6 | 144 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 25 | 0 | 0 | 1098 | 4794 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 26 | 2 | 85 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 27 | 0 | 0 | 1009 | 6504 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 28 | 1 | 45 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 29 | 0 | 801 | 7690 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 30 | 19 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 31 | 0 | 530 | 7956 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 32 | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 33 | 0 | 302 | 7135 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 34 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 35 | 0 | 140 | 5596 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 36 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 37 | 58 | 3791 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 38 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 39 | 20 | 2240 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 40 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 41 | 6 | 1138 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 42 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 43 | 2 | 507 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 44 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 45 | 1 | 195 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 46 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 47 | 67 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 48 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 49 | 21 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 50 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 51 | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 52 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 53 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 54 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 55 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 2 | 4 | 9 | 21 | 65 | 240 | 1128 | 6764 | 53971 |
Table 2. The number of graphs admitting a strictly matched involution with vertices (and edges) for
Andres et al. (2019) provided a list of graphs admitting a strictly matched involution on vertices with . In Figure 3, as a further example, we display the graphs admitting a strictly matched involution on 6 vertices.
Figure 3. The graphs admitting a strictly matched involution with 6 vertices, ordered according to their numbers of edges: fat vertices indicate clique vertices and fat edges indicate matching edges with respect to a certain (not necessarily unique) strictly matched involution
Counting by edges
The proofs of Observation 3.2 and Theorem 3.3 are given in this section. In order to simplify some arguments in the proofs, we start with an obvious lemma.
Lemma 6.1 Every graph admitting a strictly matched involution with vertices contains the graph as a (not necessarily induced) subgraph.
Proof. Let be a graph admitting a strictly matched involution with vertices. By Theorem 2.1, there is an integer with , such that the vertex set of can be partitioned into a set containing a matching on edges and a clique of size . Since the clique contains a matching on edges, the graph contains a matching of size
i.e., the graph is a subgraph of . □
We will now prove Observation 3.2 and Theorem 3.3.
Proof of Observation 3.2: We have the following.
Ad (a): Since, by Lemma 6.1, every graph admitting a strictly matched involution with vertices contains the graph as a subgraph, which is a graph with edges, (a) follows trivially.
Ad (b): Since a graph on vertices has at most edges, (b) follows trivially.
Ad (c) and (d): Let be a graph admitting a strictly matched involution with vertices, where with and . Then the number of matching edges and clique edges with respect to a fixed strictly matched involution with matching edges is
for some . Thus, for ,
and, for ,
Since all other types of edges are added pairwisely, the number of edges of is even if , i.e., if ; and the number of edges of is odd if , i.e., if . This proves (c) and (d). □
Proof of Theorem 3.3: We have the following.
Ad (a): Let be a graph admitting a strictly matched involution with vertices and edges. By Lemma 6.1, has the graph as a subgraph, which is a graph with edges. Thus, is isomorphic to if is even, respectively, is isomorphic to if is odd. Both types of graphs are obviously graphs admitting a strictly matched involution (with clique size 0, respectively, clique size 1). This proves (a).
Ad (b): Let be a graph admitting a strictly matched involution with vertices and edges. By Lemma 6.1, contains as a subgraph. Let be the subgraph on the vertex set of with the edges of the . Furthermore there are two additional edges in .
If one of these edges is adjacent to matching edges and , then, by Theorem 2.1, the other edge is also adjacent to and , moreover if is odd, then the other edge must be symmetrical to the first edge. If one of these edges is adjacent to a matching edge and incident with the isolated vertex of (in case is odd), then, by Theorem 2.1, the other edge must also be adjacent to and incident with the isolated vertex of .
We conclude that in case is even (and ), the graph is isomorphic either to or to , where is the paw graph. And in case is odd (and ), the graph is isomorphic either to or to .
As all these graphs are obviously graphs admitting a strictly matched involution, (b) is proved.
Ad (c): Let be an even number, , and be a graph admitting a strictly matched involution with vertices and edges. By Theorem 2.1, there is , so that the vertex set of can be decomposed into a clique of size and the vertex sets of two isomorphic graphs and , each with vertices, moreover the clique size is even and cannot be more than 4, thus for only the following cases are possible:
and
and
and
If we let denote the number of edges of , denote the number of edges of the graph induced by the clique , denote the number of pairs of edges between and which are not matching edges (we call them cross-edges), and denote the number of pairs of edges between and (we call them clique-connecting-edges), then we note that in Case (1) and in Case (2)
whereas in Case (3)
Therefore, we subdivide the cases (1), (2), and (3) as follows.
(1.a) and (thus and )
(1.b) and (thus and )
(1.c) and (thus and )
(2.a) and and (thus )
(2.b) and and (thus )
(2.c) and and (thus )
(2.d) and and (thus )
(2.e) and and (thus )
(2.f) and (thus and )
(3.a) (thus and and )
In the following, we refer to the names of types of graphs depicted in Figure 4.
Figure 4. The graphs occurring in the proof of Theorem 3.3 (c) and (d)
In Case (1.a), depending on whether all four cross-edges are adjacent to one certain matching edge or not, we see that is isomorphic to or , respectively.
In Case (1.b), if both cross-edges are adjacent to the edge of , the graph is isomorphic to . If only one cross-edge is adjacent to the edge of , then is isomorphic to . If none of the cross-edges is adjacent to the edge of , then is isomorphic to .
In Case (1.c), if the two edges of are connected, we obtain , otherwise we obtain .
In Case (2.a), we obtain the same as in Case (1.a), since the clique edge cannot be connected by cross-edges, thus the clique edge can be regarded as a matching edge here.
In Case (2.b), let be the matching edge that is adjacent to the two clique-connecting-edges. If the two cross-edges are adjacent to , then we obtain , otherwise we obtain as our graph .
In Case (2.c), if the four clique-connecting-edges are incident with the same vertex of the clique, we obtain , otherwise we get .
In Case (2.d), we obtain mainly the same as in Case (1.b), since the clique edge can be regarded again as a matching edge (but note that can appear in Case (2.d) only if ).
In Case (2.e), if the edge of is adjacent to a clique-connecting-edge, then we obtain . Otherwise, we obtain .
In Case (2.f), we obtain the same as in Case (1.c), since the clique edge can be regarded again as a matching edge.
In Case (3.a), we obtain .
Thus, on the one hand, each of the types of graphs on the left-hand side of Figure 4 may appear. On the other hand, these types of graphs admit a strictly matched involution (e.g., with the matching edges drawn vertically in the figure).
Ad (d): Let be an odd number, , and be a graph admitting a strictly matched involution with vertices and edges. By Theorem 2.1, there is , so that the vertex set of can be decomposed into a clique of size and the vertex sets of two isomorphic graphs and , each with vertices, moreover the clique size is odd and cannot be more than 4, thus for only the following cases are possible:
(1) and
(2) and
With the same notation as in the proof of (c), we note that in Case (1)
whereas in Case (2)
Thus, we subdivide the cases (1) and (2) as follows.
(1.a) and and (thus )
(1.b) and and (thus )
(1.c) and and (thus )
(1.d) and and (thus )
(1.e) and and (thus )
(1.f) and (thus and )
(2.a) and and (thus )
(2.b) and and (thus )
(2.c) and (thus and ) In the following, we refer again to the names of types of graphs depicted in Figure 4.
In Case (1.a), as , by the same arguments as in Case (1.a) in the proof of (c), we obtain or as graph .
In Case (1.b), if a cross-edge is adjacent to a clique-connecting edge, then we obtain . Otherwise, we obtain .
In Case (1.c) we necessarily obtain .
In Case (1.c), as , by the same arguments as in Case (1.b) in the proof of (c), we obtain or or .
In Case (1.e), if the edge of is adjacent to a clique-connecting-edge, then we obtain . Otherwise, we obtain .
In Case (1.f), as , by the same arguments as in Case (1.c) in the proof of (c), we obtain or .
In Case (2.a) we obtain .
In Case (2.b) we obtain .
In Case (2.c) we obtain again.
Thus, on the one hand, each of the types of graphs on the right-hand side of Figure 4 may appear. On the other hand, these types of graphs admit a strictly matched involution (e.g., with the matching edges drawn vertically in the figure).
The proofs of Theorem 3.3 (c) and (d) may give a good idea for the fact that in our upper bound of Theorem 3.1 and in the enumeration approach derived from Theorem 3.1 many graphs are counted multiple times, which is getting super-exponentially worse with increasing number of vertices and edges. This is the reason why in our computer program isomorphism tests consume most of the running time.
Using Observation 3.2 and Theorem 3.3 and the values from Table 1, we can determine for , see Table 3. We have implemented these values in the OEIS (OEIS Foundation Inc. (2026)) in sequence A363772.
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 |
| 3 | 1 | 2 | 3 | 3 |
| 4 | 2 | 4 | 8 | 9 |
| 5 | 2 | 9 | 21 | 25 |
| 6 | 4 | 21 | 78 | 113 |
| 7 | 4 | 65 | 343 | 545 |
| 8 | 11 | 240 | 2004 | 3841 |
| 9 | 11 | 1128 | 15337 | 31873 |
| 10 | 34 | 6764 | 141466 | 362753 |
| 11 | 34 | 53971 | 1714411 | 5112321 |
Table 1. Lower bound (second column), exact value (third column), new upper bound (fourth column), and previously known upper bound (fifth column), for the sequence
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| 0 | 1 | |||||||||||
| 1 | 1 | |||||||||||
| 2 | 1 | |||||||||||
| 3 | 1 | 0 | 1 | |||||||||
| 4 | 1 | 0 | 2 | 0 | 1 | |||||||
| 5 | 1 | 0 | 2 | 0 | 3 | 0 | 2 | 0 | 0 | 1 | ||
| 6 | 1 | 0 | 2 | 0 | 5 | 0 | 6 | 0 | 4 | |||
| 7 | 1 | 0 | 2 | 0 | 5 | 0 | 11 | 0 | 13 | |||
| 8 | 1 | 0 | 2 | 0 | 7 | 0 | 16 | 0 | ||||
| 9 | 1 | 0 | 2 | 0 | 6 | 0 | 17 | 0 | ||||
| 10 | 1 | 0 | 2 | 0 | 7 | 0 | 21 | |||||
| 11 | 1 | 0 | 2 | 0 | 6 | 0 | 19 | |||||
| 12 | 1 | 0 | 2 | 0 | 7 | 0 | ||||||
| 13 | 1 | 0 | 2 | 0 | 6 | 0 | ||||||
| 14 | 1 | 0 | 2 | 0 | 7 | |||||||
| 15 | 1 | 0 | 2 | 0 | 6 | |||||||
| 16 | 1 | 0 | 2 | 0 | ||||||||
| 17 | 1 | 0 | 2 | 0 | ||||||||
| 18 | 1 | 0 | 2 | |||||||||
| 19 | 1 | 0 | 2 | |||||||||
| 20 | 1 | 0 | ||||||||||
| 21 | 1 | 0 | ||||||||||
| 22 | 1 | |||||||||||
| 23 | 1 | |||||||||||
| 2 | 2 | 2 | 3 | 6 | 6 | 10 | 16 | 21 | 36 | 53 | 76 |
Table 3. The number of graphs admitting a strictly matched involution with edges (and vertices) for . The values for are taken from Table 2, the values for are implied by Observation 3.2 and Theorem 3.3.
The decomposition lemma
The key fact for the proof of Theorem 3.4 will be the following decomposition lemma. We start with three formulations of this main lemma. Its simple form is the following.
Lemma 7.1 (decomposition lemma, version 1: simple form) For every graph , the following statements are equivalent:
(1) admits a strictly matched involution.
(2) admits a strictly matched involution.
By induction, we get the second form.
Lemma 7.2 (decomposition lemma, version 2: aggregated form) For every graph and every , the following statements are equivalent:
(1) admits a strictly matched involution.
(2) admits a strictly matched involution.
We will use a third form of the decomposition lemma, which is derived from the second form.
Lemma 7.3 (decomposition lemma, version 3: complementary form) For every and every subgraph of , the following statements are equivalent:
The complement of admits a strictly matched involution.
admits a strictly matched involution.
We will now prove the simple form of the decomposition lemma, i.e., Lemma 7.1. The other forms (Lemmata 7.2 and 7.3}) can be obtained as easy corollaries from Lemma 7.1`.
Proof of Lemma 7.1: Assume admits a strictly matched involution . If we add a new fixed point to that is connected to every vertex of , then the mapping with
is a strictly matched, involutive graph automorphism. This proves the trivial implication (1) (2).
Now assume that admits a strictly matched involution . Let be the vertex of . If is in the fixed point set , then we may obviously delete and is still strictly matched, well-defined, and involutive. Thus, suppose that
Let . Since is connected to every vertex of , the vertex is connected to every other vertex of (as is a graph automorphism). Thus we may consider as a part of the clique, i.e., we may define a map on the vertex set of by
The map is a strictly matched involutive graph automorphism, since has the same property on and is a fixed point of connected to every other vertex, in particular, to every pair of vertices of orbit 2. This proves the non-trivial implication (2) (1). □
Proof of Lemma 7.2: Applying Lemma 7.1 inductively times implies the statement of Lemma 7.2. □
Proof of Lemma 7.3: Since is isomorphic to , the statement of Lemma 7.3 directly follows from Lemma 7.2 when substituting by and by . □
In the proof of Theorem 3.4 we will also frequently make use of the following obvious lemma.
Lemma 7.4 For every graph admitting a strictly matched involution and every edge of with , i.e., for every matching edge , we have
Using Lemma 7.3 and Lemma 7.4 we are able to give the following simple proof of Theorem 3.4.
Proof of Theorem 3.4: We have the following.
Ad (a): Since the only graph with vertices and edges is the complete graph on vertices, which is a graph admitting a strictly matched involution with matching edges and a clique of size , the assertion follows trivially.
Ad (b): For , there are only two graphs with edges. They can be obtained from the complete graph on edges by deleting either two nonadjacent or two adjacent edges. We will prove that these two graphs admit a strictly matched involution.
If is even, then the first graph can be constructed by using a clique of size 0 and adding all possible edges except for one pair of edges between two matching edges; and the second graph can be constructed by using a clique of size 2 and adding all possible edges except for one pair of edges between the two vertices of a matching edge and one of the vertices of the clique.
Similarly, if is odd, then the first graph can be constructed by using a clique of size 1 and adding all possible edges except for one pair of edges between two matching edges; and the second graph can be constructed by using a clique of size 1 and adding all possible edges except for one pair of edges between the two vertices of a matching edge and the vertex of the clique.
Ad (c): Let be a graph admitting a strictly matched involution with vertices, where , and with edges. By Lemma 7.3, the number of such graphs is the same as the number of graphs with 4 edges and without isolated vertices whose complement admits a strictly matched involution. In the table of Figure 5 all graphs with 4 edges and without isolated vertices and their complements are depicted.
Figure 5. List of all graphs with 4 edges (without isolated vertices) and their complements
It is easy to see that the 6 graph complements , , , , , and admit a strictly matched involution with the matching edges drawn vertically in bold lines.
So we only have to prove that the other 5 graph complements do not admit a strictly matched involution:
Consider first. Since none of the edges of has vertices of equal degree and the vertices of the graph are not a clique, by Lemma 7.4 the graph cannot admit a strictly matched involution.
The same argument applies to .
In , by Lemma 7.4 the only possible matching edges would be , , and , and, since these edges form a triangle, only one of them is possible. But in all three cases the three vertices not contained in the edge are not a clique. Therefore no strictly matched involution is possible for .
If we assume that admits a strictly matched involution , by Lemma 7.4 the only possible matching edges are between the vertices of degree 4, namely between the vertices 2, 3, 4, 5, and 6. Thus there are at most 2 matching edges. In order to make vertex 1 part of a clique, the clique must consist of the vertices 1 and 2, or of 1 and 6. By symmetry, we may assume that the clique consists of the vertices 1 and 2. But there is the edge , whereas the edge does not exist, which is a contradiction to the structural theorem (Theorem 2.1).
If we assume that admits a strictly matched involution, by Lemma 7.4 the only possible matching edges are at most two edges on the vertex set . However, the vertices 2 and 3 are not connected by an edge, thus not part of a clique, which is a contradiction.
Note that the graphs , , do not have more than 8 vertices. Thus we have proved that, for every ,
which proves (c).
Remark 7.5 From the proof of Theorem 3.4 (c) we may also deduce the following trivial values: As only has 8 vertices, we conclude that
As there are only two of the graphs that admit a strictly matched involution with more than 6 vertices, we have
and by similar arguments we conclude
and
Open problems and conjectures
The main open problem arising from this paper is the following.
Problem 8.1 Determine for further values of and .
Problem 8.1 might be attacked by a combinatorial approach, e.g., based on the decomposition lemma (Lemma 7.3), or by computational enumeration approaches.
Even the complexity status of our counting problems are still open, i.e., the following problems might be of further interest.
Problem 8.2 Determine the complexity of Problem 1.1.
Problem 8.3 Determine the complexity of Problem 1.2.
Problem 8.4 Determine the complexity of Problem 1.3.
In Figure 5 we listed some graphs and their complements. We observe that some graphs and their complements admit a strictly matched involution (only and and their complements), some graphs and their complements do not admit a strictly matched involution (e.g., and its complement), and there are graphs that admit a strictly matched involution but their complements do not admit a strictly matched involution (e.g., ). Thus the following might be interesting. Problem 8.5 Characterise (or determine the complexity of characterising) the class of graphs , for which neither nor its complement admits a strictly matched involution.
Problem 8.6 Characterise (or determine the complexity of characterising) the class of graphs , for which both and its complement admit a strictly matched involution.
Python3 enumeration program
Idea of the Python3 program
For fixed and , the enumeration program creates a list of graphs admitting a strictly matched involution on vertices with respect to some strictly matched involution with matching edges according to the structure theorem (Theorem 2.1) in the following way:
(Step 1) Based on a list of all graphs on vertices, for every such graph , we construct a graph with two isomorphic copies of , connected by matching edges, and a clique of size .
(Step 2) For every graph from the list of graphs from Step 1 and for every way to insert pairs of clique-connecting edges according to part (3) in the proof of Theorem 3.1, we construct a graph with the edges of and these pairs of clique-connecting edges.
(Step 3) For every graph from the list of graphs from Step 2 and for every way to insert pairs of cross edges according to part (2) in the proof of Theorem 3.1, we construct a graph with the edges of and these pairs of cross edges.
Finally, we iterate over all () and apply isomorphism tests to the union of the lists obtained from Step 3 (for all ) to get the list of all (pairwise nonisomorphic) graphs admitting a strictly matched involution with vertices (and separate this list into lists of graphs admitting a strictly matched involution with vertices and edges for ); the number of these graphs is ).
Code of the Python3 program
import sys
import networkx as nx
import networkx.algorithms.isomorphism as iso
#check whether graph G is isomorphic to a graph of a list
def isIsoTo(G,listOfGraphs):
for H in listOfGraphs:
if iso.is_isomorphic(G,H):
return True
return False
#sort out isomorphic copies from a list of graphs,
#return a reduced list
def reduceList(listOfGraphs):
listOfNonisomorphicGraphs = []
for G in listOfGraphs:
isomorphic = False
for H in listOfNonisomorphicGraphs:
if iso.is_isomorphic(G,H):
isomorphic = True
break
if not isomorphic:
listOfNonisomorphicGraphs.append(G)
return listOfNonisomorphicGraphs
#creates a graph with n isolated vertices
def edgelessGraph(n):
G = nx.Graph()
for i in range(n):
G.add_node(i)
return G
#initialises empty list of lists of graphs with n vertices
listOfAllGraphs = {0:[]}
#creates list of lists of graphs with n vertices
def createListOfAllGraphs(n):
candidates = []
candidates.append(edgelessGraph(n))
for i in range(n-1):
for j in range(i+1,n):
newItems = []
for G in candidates:
H = G.copy()
H.add_edge(i,j)
newItems.append(H)
for G in newItems:
candidates.append(G)
listOfAllGraphs[n] = reduceList(candidates)
print("Created list of graphs with ",n,
" vertices. Number: ",len(listOfAllGraphs[n]))
#enumerate all graphs admitting a strictly matched involution
#on n vertices with k matching edges
#do not yet sort out isomorphic copies
def enumerateGraphsWithSMI(n, k):
#(Step 1) initialise the list
#of all graphs admitting a strictly matched involution
#on n vertices with k matching edges by the empty list
listOfGraphsWithSMI = []
#initialise provisional list for these graphs
newItems = []
for N in listOfAllGraphs[k]:
#create union of kK2 and Ks (s=n-2k), which is a subgraph
#of every graph admitting a strictly matched involution
#on n vertices with k matching edges
#indices of vertices of Ks: 0,...,s-1
#indices of vertices of kK2: s,...,n-1
#matching edge (n-2*v-2,n-2*v-1) for v=0,...,k-1
H=edgelessGraph(n)
s = n-2*k
#create Ks --- insert "clique edges"
for v in range(s):
for b in range(v+1, s):
H.add_edge(v, b)
#create kK2 --- insert "matching edges"
for v in range(k):
H.add_edge(n-2*v-2,n-2*v-1)
#create edges in the two isomorphic copies of the graph N
# --- insert pairs of "subgraph edges"
for v in N.edges():
H.add_edges_from([(n-2*v[0]-1,n-2*v[1]-1),
(n-2*v[0]-2,n-2*v[1]-2)])
#add the created graph to the provisional list
newItems.append(H)
#(Step 2) Now create "clique-connecting edges" by bubbling(n,k)
#a pair of clique-connecting edges connects
#the ends of a matching edge to a clique vertex
#create all binom(P,m)=binom(2ˆk+n-2k-1,n-2k) combinations of
#multisets of subsets of matching edges
#on the n-2k clique vertices
#(Step 2.1): calculate P and m
twoToThePowerOfK=1
for i in range(k):
twoToThePowerOfK=twoToThePowerOfK*2
m=n-2*k
P=twoToThePowerOfK+m-1
#(Step 2.2): initialise
#A: incidence array of big set of order P
#B: multiplicity array
#start with the first possible values for A
A=[]
for i in range(P):
A.append(0)
for i in range(m):
A[i]=1
B=[]
for i in range(m):
B.append(0)
#(Step 2.3): initialise bubbling stop variable
bubblingsend=0
#(Step 2.4): big bubbling loop
while(bubblingsend==0):
#(Step 2.4a): create the actual graphs H
for G in newItems:
H = G.copy()
numberZ=0
cliquecounter=0
for i in range(P):
if(A[i]==0):
numberZ+=1
if(A[i]==1):
B[cliquecounter]=numberZ
cliquecounter+=1
for cliquecounter in range(m):
numberZ=B[cliquecounter]
twoToThePowerOfX=twoToThePowerOfK//2
for vv in range(k):
if(numberZ//twoToThePowerOfX>0):
#add pair of "clique-connecting edges"
H.add_edges_from([(cliquecounter,n-2*vv-1),
(cliquecounter,n-2*vv-2)])
numberZ=numberZ-twoToThePowerOfX
twoToThePowerOfX=twoToThePowerOfX//2
listOfGraphsWithSMI.append(H)
#(Step 2.4b): technical bubbling
leadpointer=-1
pointercount=0
Aindex=0
while((Aindex<P-1) and (leadpointer<0)):
if(A[Aindex]==1):
pointercount+=1
if(A[Aindex+1]==0):
leadpointer=Aindex
Aindex+=1
if(leadpointer<0):
bubblingsend=1
if(bubblingsend==0):
A[leadpointer]=0
A[leadpointer+1]=1
for smaller in range(pointercount-1):
A[smaller]=1
for middle in range(pointercount-1,leadpointer):
A[middle]=0
#end of bubbling(n,k)
#(Step 3) add "cross edges" between pairs of matching edges
for i in range(k-1):
for v in range(i+1,k):
newItems = []
for G in listOfGraphsWithSMI:
H = G.copy()
H.add_edges_from([(n-2*i-1,n-2*v-2),
(n-2*i-2,n-2*v-1)])
newItems.append(H)
#listOfGraphsWithSMI += newItems
for G in newItems:
listOfGraphsWithSMI.append(G)
#return final list
return listOfGraphsWithSMI
#start main program
#define lower and upper bound xxx of calculation
xxxLower = 0
xxxUpper = 11
#create list of all graphs with <=n/2 vertices
for n in range(xxxUpper//2+1):
createListOfAllGraphs(n)
print("Number A[n] of graphs admitting a ",
"strictly matched involution with n vertices:")
#create list of all graphs with SMI and test
#sort out isomorphic copies
for n in range(xxxLower,xxxUpper+1):
listOfGraphsWithSMI = []
for y in range(n*(n-1)//2+1):
listOfGraphsWithSMI.append([])
for k in range(n//2+1):
temporaryList = enumerateGraphsWithSMI(n,k)
newList = []
for y in range(n*(n-1)//2+1):
newList.append([])
for GG in temporaryList:
newList[GG.number_of_edges()].append(GG)
for y in range(n*(n-1)//2+1):
for GG in newList[y]:
if not isIsoTo(GG,listOfGraphsWithSMI[y]):
listOfGraphsWithSMI[y].append(GG)
sum=0
for y in range(n*(n-1)//2+1):
sum += len(listOfGraphsWithSMI[y])
print("n =",n," --> A[n] =",sum)
print("Results by number of edges:")
for y in range(n*(n-1)//2+1):
print(len(listOfGraphsWithSMI[y])," ",end=’’)
print()
References
References
- [1]M. Aljohani, S. Lazaar, A. Mhemdi, N. Zidani, and A. Aboubakr. Numerical studies of some partial orderings on a set with height at most one. Boletim da Sociedade Paranaense de Matemática, 43:1–12, 2025. doi: 10.5267/bspm.75758.DOI
- [2]T. Amdeberhan, V. De Angelis, A. Dixit, V. H. Moll, and C. Vignat. From sequences to polynomials and back, via operator orderings. Journal of Mathematical Physics, 54:15 pp., 2013. 123502.DOI
- [3]S. D. Andres, M. A. Huggan, F. Mc Inerney, and R. J. Nowakowski. The orthogonal colouring game. Theoretical Computer Science, 795:312–325, 2019.DOI
- [4]S. D. Andres, M. A. Huggan, F. Mc Inerney, and R. J. Nowakowski. Corrigendum to “The orthogonal colouring game” [Theor. Comput. Sci. 795 (2019) 312–325]. Theoretical Computer Science, 842:133–135, 2020.DOI
- [5]S. D. Andres, F. Dross, M. A. Huggan, F. Mc Inerney, and R. J. Nowakowski. The complexity of two colouring games. Algorithmica, 85:1067–1090, 2023.
- [6]P. Bala. Integer sequences that become periodic on reduction modulo k for all k, 2017. Published electronically at https://oeis.org/A047974/A047974.1.pdf.
- [7]J. Burns, E. Dolzhenko, N. Jonoska, T. Muche, and M. Saito. Four-regular graphs with rigid vertices associated to DNA recombination. Discrete Applied Mathematics, 161:1378–1394, 2013.
- [8]A. M. Davies, U. Larsson, R. Milley, R. J. Nowakowski, C. P. Santos, and A. N. Siegel. Combinatorial game theory monoids and their absolute restrictions: a survey. In U. Larsson, editor, Games of no chance 6, Mathematical Sciences Research Institute Publications, pages 1–24. Cambridge University Press, 2025.
- [9]T. Halverson and M. Reeks. Gelfand models for diagram algebras. Journal of Algebraic Combinatorics, 41:229–255, 2015.
- [10]W. Johnson. The combinatorial game theory of well-tempered scoring games. International Journal of Game Theory, 43:415–438, 2014.arxiv.org/abs/1112.3610
- [11]U. Larsson, R. J. Nowakowski, J. P. Neto, and C. P. Santos. Guaranteed scoring games. Electronic Journal of Combinatorics, 23:29 pp., 2016. Article P3.27.arxiv.org/abs/1505.07905
- [12]U. Larsson, R. J. Nowakowski, and C. P. Santos. Game comparison through play. Theoretical Computer Science, 725:52–63, 2018a.DOI
- [13]U. Larsson, R. J. Nowakowski, and C. P. Santos. Games with guaranteed scores and waiting moves. International Journal of Game Theory, 47:653–671, 2018b.DOI
- [14]U. Larsson, R. J. Nowakowski, and C. P. D. Santos. Scoring games: the state of play. In U. Larsson, editor, Games of no chance 5, Mathematical Sciences Research Institute Publications, pages 89–111. Cambridge University Press, 2019.DOI
- [15]U. Larsson, R. J. Nowakowski, and C. P. Santos. Absolute combinatorial game theory. In U. Larsson, editor, Games of no chance 6, Mathematical Sciences Research Institute Publications, pages 99–134. Cambridge University Press, 2025.
- [16]G. Latouche and P. Taylor. A stochastic fluid model for an ad hoc mobile network. Queueing Systems: Theory and Applications, 63:109–129, 2009.DOI
- [18]J. Quaintance and H. Kwong. Permutations and combinations of colored multisets. Journal of Integer Sequences, 13:12 pp., 2010. Article 10.2.6.
- [19]R. K. Rai, U. Larsson, and N. Patel. Discrete Richman-bidding scoring games. International Journal of Game Theory, 50:695–728, 2021.arxiv.org/abs/2003.05635
- [20]I. Režan. Untersuchungen zur Anzahl von Graphen mit strikt gepaarter Involution. Master thesis, Fern-Universität in Hagen, Germany, 2020.
- [21]S. J. Seo and P. J. Slater. Competition parameters of a graph. AKCE International Journal of Graphs and Combinatorics, 4:183–190, 2007.
- [22]F. Stewarts. Scoring play combinatorial games. In U. Larsson, editor, Games of no chance 5, Mathematical Sciences Research Institute Publications, pages 447–468. Cambridge University Press, 2019.DOI



