betaFeedback

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 GG is a self-inverse graph automorphism ff with the properties that the fixed point set of ff induces a complete subgraph in GG and, for the vertices that are no fixed points, every vertex is connected to its image under ff by an edge. Andres, Huggan, Mc Inerney, and Nowakowski (2019) determined upper and lower bounds for the number A(n)A(n) of graphs admitting a strictly matched involution on nn vertices. We improve the upper bound and we compute the exact values for the number A(n)A(n) for all n≤11n\leq11. Furthermore, we use combinatorial enumeration techniques and a decomposition lemma to determine the number C(n,m)C(n,m) of graphs admitting a strictly matched involution with nn vertices and mm edges for several infinite classes of pairs (n,m)(n,m).

Introduction

Let G=(V,E)G=(V,E) be a (simple finite) graph. A graph automorphism of GG is a bijective map σ:V⟶V\sigma: V \longrightarrow V with the property that, for every two vertices v,w∈Vv,w \in V, the vertices vv and ww are connected by an edge if, and only if, the vertices σ(v)\sigma(v) and σ(w)\sigma(w) are connected by an edge. An involution of GG is a graph automorphism σ\sigma with σ(σ(v))=v\sigma(\sigma(v))=v for every vertex v∈Vv \in V. By an involution σ\sigma of GG, the vertex set of GG is separated into two subsets: the set

F1(G,σ):={v∈V∣σ(v)=v}F_1(G,\sigma):=\{v \in V \mid\sigma(v)=v\}

of fixed points and the set

F2(G,σ):=V∖F1(G,σ)F_2(G,\sigma):=V \setminus F_1(G,\sigma)

of points of orbit 2. An involution σ\sigma of GG is called strictly matched if

  1. ∀v∈F2(G,σ):vσ(v)∈E\forall v \in F_2(G,\sigma): v\sigma(v) \in E and

  1. F1(G,σ)F_1(G,\sigma) induces a clique, i.e., a graph in which every two vertices are connected by an edge.

Then, an edge of type vσ(v)v\sigma(v) is called a matching edge of the pair (G,σ)(G,\sigma). 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 nn vertices and mm edges for m,n∈Nm,n \in\mathbb{N}. Moreover, for m,n∈Nm,n \in\mathbb{N}, let

  • A(n)A(n) denote the number of graphs admitting a strictly matched involution with nn vertices,

  • B(m)B(m) denote the number of graphs admitting a strictly matched involution with mm edges, and

  • C(n,m)C(n,m) denote the number of graphs admitting a strictly matched involution with nn vertices and mm edges,

respectively, up to isomorphism. We aim to obtain partial answers to the following problems.

Problem 1.1 Given n∈Nn \in\mathbb{N} as input, determine A(n)A(n).

Problem 1.2 Given m∈Nm \in\mathbb{N} as input, determine B(m)B(m).

Problem 1.3 Given n,m∈Nn,m \in\mathbb{N} as input, determine C(n,m)C(n,m).

As main results we determine the exact values C(n,m)C(n,m) for several infinite classes of pairs (n,m)(n,m). Furthermore, we improve a general upper bound given by Andres et al. (2019) for the numbers A(n)A(n). Finally, we implement a computer program that determines A(n)A(n) and C(n,m)C(n,m) for 0≤n≤110 \leq n \leq11.

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 N\mathbb{N} denote the set {0,1,2,3,…}\{0,1,2,3,\ldots\} of nonnegative integers. For k∈Nk \in\mathbb{N}, let (Vk)\binom{V}{k} denote the set of all subsets of VV with exactly kk elements. A graph is a pair (V,E)(V,E) consisting of a finite set VV, the set of vertices, and a set E⊆(V2)E \subseteq\binom{V}{2}, the set of edges. By this definition, all graphs in this paper are assumed to be simple and finite. Edges {v,w}∈E\{v,w\} \in E are usually written as vwvw. Two graphs G=(V,E)G=(V,E) and G′=(V′,E′)G'=(V',E') are isomorphic if there is a bijective map f:V⟶V′f:V \longrightarrow V' satisfying

∀v,w∈V:(vw∈E⟺f(v)f(w)∈E′).\forall v,w \in V:\quad(vw \in E \Longleftrightarrow f(v)f(w) \in E').

Such a map is called a graph isomorphism from GG to G′G'. Following standard graph theory conventions, isomorphic graphs are considered as the same objects. A graph automorphism of GG is a graph isomorphism from GG to GG.

For n∈Nn \in\mathbb{N}, let KnK_n denote the clique (or also called complete graph) on nn vertices, i.e.,

Kn=(V,(V2))K_n = \left(V, \binom{V}{2}\right)

with V={1,…,n}V = \{1, \ldots, n\}. Some special graphs admitting a strictly matched involution with 4 vertices are the 4-cycle, denoted by C4C_4, and the paw (sometimes also called 3-pan), which is denoted by PP in this paper, see Figure 1. The disjoint union of two graphs G1G_1 and G2G_2, i.e., a graph (V1′∪V2′,E1′∪E2′)(V'_1 \cup V'_2, E'_1 \cup E'_2) for an isomorphic copy (V1′,E1′)(V'_1, E'_1) of G1G_1 and an isomorphic copy (V2′,E2′)(V'_2, E'_2) of G2G_2 with V1′∩V2′=∅V'_1 \cap V'_2 = \emptyset, is denoted by G1∪G2G_1 \cup G_2; and, for n∈Nn \in\mathbb{N}, the nn-fold disjoint union nG1nG_1 is defined recursively by 0G1:=(∅,∅)0G_1 := (\emptyset, \emptyset) and nG1:=((n−1)G1)∪G1nG_1 := ((n - 1)G_1) \cup G_1 for n∈N∖{0}n \in\mathbb{N} \setminus\{0\}. The complete join of two graphs G1G_1 and G2G_2, i.e., the graph that is generated from the disjoint union G1∪G2G_1 \cup G_2 by connecting every vertex of the copy of G1G_1 with every vertex of the copy of G2G_2, is denoted by G1∨G2G_1 \vee G_2. For a graph G=(V,E)G = (V, E), let G‾\overline{G} denote the complement of GG, and, if E′⊆EE' \subseteq E, then G−E′G - E' is the graph (V,E∖E′)(V, E \setminus E'). If v∈Vv \in V, then G−vG - v is the subgraph of GG induced by V∖{v}V \setminus\{v\}, i.e., the graph obtained from GG by deleting the vertex vv and all edges containing vv. The degree dG(v)d_G(v) of a vertex vv in GG is the number of the edges containing vv.

The graphs admitting a strictly matched involution with 4 vertices

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 G=(V(G),E(G))G = (V(G), E(G)) on nn vertices admitting a strictly matched involution has a partition of its vertex set into three (possibly empty) vertex subsets inducing a clique C=(V(C),E(C))C = (V(C), E(C)) of size n−2kn - 2k and two isomorphic graphs H=(V(H),E(H))H = (V(H), E(H)) and H′=(V(H′),E(H′))H' = (V(H'), E(H')), each of size kk, for some k∈Nk \in\mathbb{N} with 0≤k≤⌊n2⌋0 \leq k \leq\left\lfloor\frac{n}{2} \right\rfloor, respectively. Moreover, there is a graph isomorphism σ~:V(H)⟶V(H′)\tilde{\sigma}: V(H) \longrightarrow V(H') such that

(1) for every pair (v,v′)(v, v') of vertices v∈V(H)v \in V(H) and v′∈V(H′)v' \in V(H') with v′=σ~(v)v' = \tilde{\sigma}(v) and every vertex x∈V(C)x \in V(C), either both or none of vxvx and v′xv'x are edges in E(G)E(G);

(2) for every pair (v,v′)(v, v') of vertices v∈V(H)v \in V(H) and v′∈V(H′)v' \in V(H') with v′=σ~(v)v' = \tilde{\sigma}(v), we have vv′∈E(G)vv' \in E(G);

(3) for every two pairs (v,v′)(v, v') and (w,w′)(w, w') of vertices with v,w∈V(H)v, w \in V(H) and v′,w′∈V(H′)v', w' \in V(H'), v′=σ~(v)v' = \tilde{\sigma}(v), and w′=σ~(w)w' = \tilde{\sigma}(w), either both or none of vw′vw' and v′wv'w are edges in E(G)E(G).

We remark that the graph isomorphism σ~\widetilde{\sigma} between the subgraphs HH and H′H' in Theorem 2.1 can be extended to a strictly matched involution σ\sigma of the whole graph GG by defining

σ(v)={σ~(v)if v∈V(H);σ~−1(v)if v∈V(H′);vif v∈C.\sigma(v) = \begin{cases} \widetilde{\sigma}(v) & \text{if } v \in V(H);\\ \widetilde{\sigma}^{-1}(v) & \text{if } v \in V(H');\\ v & \text{if } v \in C. \end{cases}

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 σ\sigma according to Theorem 2.1 and the five different types of edges of such a graph with regard to σ\sigma. The edges of type (1), (2), and (3) refer to (1), (2), and (3) in Theorem 2.1.

  1. pairs of clique-connecting edges, i.e., edges implied by Theorem 2.1 (1);

  1. matching edges (cf. Theorem 2.1 (2));

  1. pairs of cross edges, i.e., the edges implied by Theorem 2.1 (3);

  1. pairs of subgraph edges, i.e., the edges of HH and H′H'; and

  1. clique edges, i.e., the edges induced by CC.

However, there might be many ways of such a decomposition, depending on the choice of HH, CC, and the matching edges. For example, in the worst case, i.e., if GG is the complete graph KnK_n on nn vertices, there are

d(n)=∑k=0⌊n/2⌋(n2k)22k∏j=1k(2j−1)=∑k=0⌊n/2⌋(n2k)(2kk)k!=∑k=0⌊n/2⌋n!k!(n−2k)!d(n) = \sum_{k=0}^{\left\lfloor n/2 \right\rfloor} \binom{n}{2k} 2^{2k} \prod_{j=1}^{k}(2j-1) = \sum_{k=0}^{\left\lfloor n/2 \right\rfloor} \binom{n}{2k} \binom{2k}{k} k! = \sum_{k=0}^{\left\lfloor n/2 \right\rfloor} \frac{n!}{k!(n-2k)!}

ways to obtain such a decomposition (C,H,H′)(C, H, H') of the vertex set of GG together with a graph isomorphism σ~:H⟶H′\widetilde{\sigma}: H \longrightarrow H' as

  • (n2k)=(nn−2k)\binom{n}{2k}=\binom{n}{n-2k} is the number of ways to choose n−2kn-2k vertices for the clique CC,

  • ∏j=1k(2j−1)\prod_{j=1}^{k}(2j-1) is the number of perfect matchings in a K2kK_{2k}, and

  • there are 2k2^k ways in total to choose which vertex of a matching edge belongs to HH.

We remark that the numbers d(n)d(n) 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 nn 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 k∈N∖{0}k\in\mathbb{N}\setminus\{0\}, it is kk-periodic modulo kk. 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 (C,H,H′)(C,H,H') of the complete graph KnK_n with respect to a graph isomorphism σ~\widetilde{\sigma} from HH to H′H' (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 nn 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 A(n)A(n) of (isomorphism classes of) graphs admitting a strictly matched involution with nn 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 g(n)g(n) of all (isomorphism classes of) graphs with nn 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 n∈Nn\in\mathbb{N},

A(n)≥g(⌊n2⌋).A(n)\geq g\left(\left\lfloor\frac{n}{2}\right\rfloor\right).

Theorem 2.3 (Andres et al. (2019), Thm 11) For every n∈Nn\in\mathbb{N},

A(n)≤∑k=0⌊n2⌋g(k)2(k2)2(n−2k)k.A(n)\leq\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}g(k)2^{\binom{k}{2}}2^{(n-2k)k}.

Our counting results

The first result of the present paper is the following improvement of Theorem 2.3.

Theorem 3.1 For every n∈Nn \in\mathbb{N},

A(n)≤∑k=0⌊n2⌋g(k)2(k2)(2k+n−2k−1n−2k).A(n) \le\sum_{k=0}^{\left\lfloor\frac{n}{2} \right\rfloor} g(k)2^{\binom{k}{2}}\binom{2^k+n-2k-1}{n-2k}.

Moreover, we use the construction of Theorem 3.1 to develop a computer program that enumerates and counts the number C(n,m)C(n,m) of (isomorphism classes of) graphs admitting a strictly matched involution with nn vertices and mm edges. Thereby, we obtain all values of C(n,m)C(n,m) with 0≤n≤110 \le n \le11. Furthermore, we determine the following exact values for C(n,m)C(n,m) for some pairs (n,m)(n,m), as given in Observation 3.2, Theorem 3.3, and Theorem 3.4.

Observation 3.2 Let m,n∈Nm,n \in\mathbb{N}. Then

(a) C(n,m)=0C(n,m)=0 if m<⌊n2⌋m < \left\lfloor\frac{n}{2} \right\rfloor;

(b) C(n,m)=0C(n,m)=0 if m>(n2)m > \binom{n}{2};

(c) C(n,m)=0C(n,m)=0 if m≡0(mod2)m \equiv0 \pmod{2} and n≡2,3(mod4)n \equiv2,3 \pmod{4};

(d) C(n,m)=0C(n,m)=0 if m≡1(mod2)m \equiv1 \pmod{2} and n≡0,1(mod4)n \equiv0,1 \pmod{4}.

Theorem 3.3 Let n∈Nn \in\mathbb{N}. Then

(a) C(n,m)=1C(n,m)=1 if m=⌊n2⌋m=\left\lfloor\frac{n}{2} \right\rfloor;

(b) C(n,m)=2C(n,m)=2 if m=⌊n2⌋+2m=\left\lfloor\frac{n}{2} \right\rfloor+2 and n≥4n \ge4;

(c) C(n,m)=7C(n,m)=7 if m=⌊n2⌋+4m=\left\lfloor\frac{n}{2} \right\rfloor+4, n≡0(mod2)n \equiv0 \pmod{2}, and n≥8n \ge8;

(d) C(n,m)=6C(n,m)=6 if m=⌊n2⌋+4m=\left\lfloor\frac{n}{2} \right\rfloor+4, n≡1(mod2)n \equiv1 \pmod{2}, and n≥8n \ge8.

Theorem 3.4 Let n∈Nn \in\mathbb{N}. Then

(a) C(n,m)=1C(n,m)=1 if m=(n2)m=\binom{n}{2};

(b) C(n,m)=2C(n,m)=2 if m=(n2)−2m=\binom{n}{2}-2 and n≥4n \ge4;

(c) C(n,m)=6C(n,m)=6 if m=(n2)−4m=\binom{n}{2}-4 and n≥8n \ge8.

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 B(m)B(m) of (isomorphism classes of) graphs admitting a strictly matched involution with mm edges, i.e., the entries of the sequence A363772 in the OEIS (OEIS Foundation Inc. (2026))) for 0≤m≤110 \le m \le11.

Proof of the improved upper bound

Proof of Theorem 3.1. Let GG be a graph admitting a strictly matched involution with nn vertices. By Theorem 2.1, the vertex set of GG can be partitioned in two subsets VV and V′V', each of cardinality kk for some k∈Nk \in\mathbb{N} with 0≤k≤⌊n2⌋0 \le k \le\left\lfloor\frac{n}{2} \right\rfloor, and a subset WW of cardinality n−2kn-2k such that WW induces a complete graph C=(W,(W2))C=\left(W,\binom{W}{2}\right) and VV and V′V' induce two isomorphic graphs H=(V,E)H=(V,E) and H′=(V′,E′)H'=(V',E'). 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.

  1. We have g(k)g(k) many possibilities to choose the edges in EE.

  1. For each of the (k2)\binom{k}{2} unordered pairs {(v,v′),(w,w′)}\{(v,v'),(w,w')\} of pairs (v,v′)(v,v') and (w,w′)(w,w') of corresponding matched vertices v,w∈Vv,w \in V and v′,w′∈V′v',w' \in V', by property (3) in Theorem 2.1, we have two choices: either the crossing edges vw′vw' and v′wv'w are both in GG or none of them; this gives us 2(k2)2^{\binom{k}{2}} choices.

  1. By property (1) in Theorem 2.1, each of the n−2kn-2k vertices in the clique CC is adjacent to each vertex of one of the 2k2^k subsets of the partition VV. Since the vertices of the clique are indistinguishable, this is equivalent to putting K:=n−2kK:=n-2k indistinguishable balls in N:=2kN:=2^k numbered cases (possibly several balls in a case). Thus we get as many choices as the number of KK-combinations of NN with repetition, which is

(N+K−1K)=(2k+n−2k−1n−2k).\binom{N+K-1}{K}=\binom{2^k+n-2k-1}{n-2k}.

As the three choices are independent, we get in total

g(k)2(k2)(2k+n−2k−1n−2k)g(k)2^{\binom{k}{2}}\binom{2^k+n-2k-1}{n-2k}

ways to choose the edges for fixed kk, and summing over all possible kk gives the upper bound for A(n)A(n) in the theorem. □\square

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 KK-variations of NN (for K=n−2kK=n-2k and N=2kN=2^k)

NK=(2k)n−2k=2(n−2k)k.N^K=(2^k)^{n-2k}=2^{(n-2k)k}.

instead of the number of KK-combinations of NN. As the number of KK-variations of NN is an upper bound for the number of KK-combinations of NN we have

(2k+n−2k−1n−2k)≤2(n−2k)k,\binom{2^k+n-2k-1}{n-2k}\le2^{(n-2k)k},

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 A(n)A(n) for 0≤n≤100 \le n \le10. Theorem 3.1 gives an improved idea how to enumerate the graphs admitting a strictly matched involution on nn 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 (A(n))n∈N(A(n))_{n\in\mathbb{N}} for all n∈Nn \in\mathbb{N} in the range 0≤n≤110 \le n \le11, thus, being able to deal with the case n=11n = 11, too. The running time for 0≤n≤90 \le n \le9 on a standard laptop was in 38 seconds, the case n=10n = 10 needed 27 minutes, and the case n=11n = 11 more than 31 hours.

We implemented the values A(n)A(n) 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 nn. However, there are still large significant gaps between the lower and new upper bound and the exact values of A(n)A(n) for large nn. Thus further improvements of the bounds might be an interesting topic of further research.

Moreover, with the program we indeed determined the values for C(n,m)C(n,m) for all 0≤n≤110 \le n \le11 and 0≤m≤(n2)0 \le m \le\binom{n}{2}. The results are displayed in Table 2.

m\nm \backslash n01234567891011
0110000000000
1111000000000
2011000000000
3100110000000
4220011000000
5002200110000
6130022000000
7055002200000
8200760000000
90611007600000
1010016170000000
11413002119000000
1200304000000000
13214006257000000
1400417400000000
1511100140155000000
16050128000000000
175002923830000000
18040175000000000
192005108700000000
20028199000000000
2110077517450000000
22161840000000000
2300987309000000000
2461440000000000
25001098479400000000
262850000000000
27001009650400000000
281450000000000
2908017690000000000
301900000000000
3105307956000000000
32600000000000
3303027135000000000
34200000000000
3501405596000000000
36100000000000
375837910000000000
38000000000000
392022400000000000
40000000000000
41611380000000000
42000000000000
4325070000000000
44000000000000
4511950000000000
46000000000000
476700000000000
48000000000000
492100000000000
50000000000000
51600000000000
52000000000000
53200000000000
54000000000000
55100000000000
A(n)A(n)11124921652401128676453971

Table 2. The number C(n,m)C(n,m) of graphs admitting a strictly matched involution with nn vertices (and mm edges) for n≤11n \le11

Andres et al. (2019) provided a list of graphs admitting a strictly matched involution on nn vertices with 0≤n≤50 \le n \le5. 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 nn vertices contains the graph ⌊n2⌋K2\left\lfloor\frac{n}{2} \right\rfloor K_2 as a (not necessarily induced) subgraph.

Proof. Let GG be a graph admitting a strictly matched involution with nn vertices. By Theorem 2.1, there is an integer kk with 0≤k≤⌊n2⌋0 \le k \le\left\lfloor\frac{n}{2} \right\rfloor, such that the vertex set of GG can be partitioned into a set containing a matching on kk edges and a clique of size n−2kn-2k. Since the clique contains a matching on ⌊n−2k2⌋\left\lfloor\frac{n-2k}{2} \right\rfloor edges, the graph GG contains a matching of size

k+⌊n−2k2⌋=⌊n2⌋,k+\left\lfloor\frac{n-2k}{2} \right\rfloor=\left\lfloor\frac{n}{2} \right\rfloor,

i.e., the graph ⌊n2⌋K2\left\lfloor\frac{n}{2} \right\rfloor K_2 is a subgraph of GG. □

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 nn vertices contains the graph ⌊n2⌋K2\left\lfloor\frac{n}{2} \right\rfloor K_2 as a subgraph, which is a graph with ⌊n2⌋\left\lfloor\frac{n}{2} \right\rfloor edges, (a) follows trivially.

Ad (b): Since a graph on nn vertices has at most (n2)\binom{n}{2} edges, (b) follows trivially.

Ad (c) and (d): Let GG be a graph admitting a strictly matched involution σ\sigma with nn vertices, where n=4ℓ+cn=4\ell+c with ℓ∈N\ell\in\mathbb{N} and c∈{0,1,2,3}c \in\{0,1,2,3\}. Then the number m0(n)m_0(n) of matching edges and clique edges with respect to a fixed strictly matched involution with kk matching edges is

m0(n)=k+(n−2k2)=k+(4ℓ+c−2k)(4ℓ+c−2k−1)2=k+4L2+c2−c+2k2≡(c2)(mod2),\begin{aligned} m_0(n)&=k+\binom{n-2k}{2}\\ &=k+\frac{(4\ell+c-2k)(4\ell+c-2k-1)}{2}\\ &=k+\frac{4L}{2}+\frac{c^2-c+2k}{2}\\ &\equiv\binom{c}{2}\pmod2, \end{aligned}

for some L∈ZL \in\mathbb{Z}. Thus, for c∈{0,1}c \in\{0,1\},

m0(n)≡(c2)≡0(mod2);m_0(n)\equiv\binom{c}{2}\equiv0\pmod2;

and, for c∈{2,3}c \in\{2,3\},

m0(n)≡(c2)≡1(mod2).m_0(n)\equiv\binom{c}{2}\equiv1\pmod2.

Since all other types of edges are added pairwisely, the number of edges of GG is even if c∈{0,1}c \in\{0,1\}, i.e., if n≡0,1(mod4)n \equiv0,1\pmod4; and the number of edges of GG is odd if c∈{2,3}c \in\{2,3\}, i.e., if n≡2,3(mod4)n \equiv2,3\pmod4. This proves (c) and (d). □

Proof of Theorem 3.3: We have the following.

Ad (a): Let GG be a graph admitting a strictly matched involution with nn vertices and ⌊n2⌋\left\lfloor\frac{n}{2} \right\rfloor edges. By Lemma 6.1, GG has the graph ⌊n2⌋K2\left\lfloor\frac{n}{2} \right\rfloor K_2 as a subgraph, which is a graph with ⌊n2⌋\left\lfloor\frac{n}{2} \right\rfloor edges. Thus, GG is isomorphic to ⌊n2⌋K2\left\lfloor\frac{n}{2} \right\rfloor K_2 if nn is even, respectively, GG is isomorphic to ⌊n2⌋K2∪K1\left\lfloor\frac{n}{2} \right\rfloor K_2 \cup K_1 if nn 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 GG be a graph admitting a strictly matched involution with nn vertices and m=⌊n2⌋+2m = \left\lfloor\frac{n}{2} \right\rfloor+ 2 edges. By Lemma 6.1, GG contains ⌊n2⌋K2\left\lfloor\frac{n}{2} \right\rfloor K_2 as a subgraph. Let G′G' be the subgraph on the vertex set of GG with the edges of the ⌊n2⌋K2\left\lfloor\frac{n}{2} \right\rfloor K_2. Furthermore there are two additional edges in GG.

If one of these edges is adjacent to matching edges ee and ff, then, by Theorem 2.1, the other edge is also adjacent to ee and ff, moreover if nn is odd, then the other edge must be symmetrical to the first edge. If one of these edges is adjacent to a matching edge ee and incident with the isolated vertex of G′G' (in case nn is odd), then, by Theorem 2.1, the other edge must also be adjacent to ee and incident with the isolated vertex of G′G'.

We conclude that in case nn is even (and n≥4n \ge4), the graph GG is isomorphic either to C4∪(⌊n2⌋−2)K2C_4 \cup\left(\left\lfloor\frac{n}{2} \right\rfloor- 2\right) K_2 or to P∪(⌊n2⌋−2)K2P \cup\left(\left\lfloor\frac{n}{2} \right\rfloor- 2\right) K_2, where PP is the paw graph. And in case nn is odd (and n≥5n \ge5), the graph GG is isomorphic either to K1∪C4∪(⌊n2⌋−2)K2K_1 \cup C_4 \cup\left(\left\lfloor\frac{n}{2} \right\rfloor- 2\right) K_2 or to K3∪(⌊n2⌋−1)K2K_3 \cup\left(\left\lfloor\frac{n}{2} \right\rfloor- 1\right) K_2.

As all these graphs are obviously graphs admitting a strictly matched involution, (b) is proved.

Ad (c): Let nn be an even number, n≥8n \ge8, and GG be a graph admitting a strictly matched involution with nn vertices and m=n2+4m = \frac{n}{2} + 4 edges. By Theorem 2.1, there is k∈Nk \in\mathbb{N}, so that the vertex set of GG can be decomposed into a clique CC of size s=n−2ks = n - 2k and the vertex sets of two isomorphic graphs HH and H′H', each with kk vertices, moreover the clique size is even and cannot be more than 4, thus for GG only the following cases are possible:

  1. s=0s = 0 and k=n2k = \frac{n}{2}

  1. s=2s = 2 and k=n2−1k = \frac{n}{2} - 1

  1. s=4s = 4 and k=n2−2k = \frac{n}{2} - 2

If we let m(H)m(H) denote the number of edges of HH, m(C)m(C) denote the number of edges of the graph induced by the clique CC, mam_a denote the number of pairs of edges between HH and H′H' which are not matching edges (we call them cross-edges), and mbm_b denote the number of pairs of edges between HH and CC (we call them clique-connecting-edges), then we note that in Case (1) and in Case (2)

m(H)+ma+mb=2,m(H) + m_a + m_b = 2,

whereas in Case (3)

m(H)+ma+mb=0.m(H) + m_a + m_b = 0.

Therefore, we subdivide the cases (1), (2), and (3) as follows.

(1.a) m(C)=0m(C) = 0 and m(H)=0m(H) = 0 (thus ma=2m_a = 2 and mb=0m_b = 0)

(1.b) m(C)=0m(C) = 0 and m(H)=1m(H) = 1 (thus ma=1m_a = 1 and mb=0m_b = 0)

(1.c) m(C)=0m(C) = 0 and m(H)=2m(H) = 2 (thus ma=0m_a = 0 and mb=0m_b = 0)

(2.a) m(C)=1m(C)=1 and m(H)=0m(H)=0 and ma=2m_a=2 (thus mb=0m_b=0)

(2.b) m(C)=1m(C)=1 and m(H)=0m(H)=0 and ma=1m_a=1 (thus mb=1m_b=1)

(2.c) m(C)=1m(C)=1 and m(H)=0m(H)=0 and ma=0m_a=0 (thus mb=2m_b=2)

(2.d) m(C)=1m(C)=1 and m(H)=1m(H)=1 and ma=1m_a=1 (thus mb=0m_b=0)

(2.e) m(C)=1m(C)=1 and m(H)=1m(H)=1 and ma=0m_a=0 (thus mb=1m_b=1)

(2.f) m(C)=1m(C)=1 and m(H)=2m(H)=2 (thus ma=0m_a=0 and mb=0m_b=0)

(3.a) m(C)=6m(C)=6 (thus m(H)=0m(H)=0 and ma=0m_a=0 and mb=0m_b=0)

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 GG is isomorphic to G3G_3 or G2G_2, respectively.

In Case (1.b), if both cross-edges are adjacent to the edge of HH, the graph GG is isomorphic to G1G_1. If only one cross-edge is adjacent to the edge of HH, then GG is isomorphic to G3G_3. If none of the cross-edges is adjacent to the edge of HH, then GG is isomorphic to G2G_2.

In Case (1.c), if the two edges of HH are connected, we obtain G3G_3, otherwise we obtain G2G_2.

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 ee be the matching edge that is adjacent to the two clique-connecting-edges. If the two cross-edges are adjacent to ee, then we obtain G7G_7, otherwise we obtain G6G_6 as our graph GG.

In Case (2.c), if the four clique-connecting-edges are incident with the same vertex of the clique, we obtain G4G_4, otherwise we get G5G_5.

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 G2G_2 can appear in Case (2.d) only if n≥10n \ge10).

In Case (2.e), if the edge of HH is adjacent to a clique-connecting-edge, then we obtain G7G_7. Otherwise, we obtain G6G_6.

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 G1G_1.

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 nn be an odd number, n≥9n \ge9, and GG be a graph admitting a strictly matched involution with nn vertices and m=n−12+4m = \frac{n-1}{2} + 4 edges. By Theorem 2.1, there is k∈Nk \in\mathbb{N}, so that the vertex set of GG can be decomposed into a clique CC of size s=n−2ks = n - 2k and the vertex sets of two isomorphic graphs HH and H′H', each with kk vertices, moreover the clique size is odd and cannot be more than 4, thus for GG only the following cases are possible:

(1) s=1s = 1 and k=n−12k = \frac{n-1}{2}

(2) s=3s = 3 and k=n−12−1k = \frac{n-1}{2} - 1

With the same notation as in the proof of (c), we note that in Case (1)

m(H)+ma+mb=2,m(H) + m_a + m_b = 2,

whereas in Case (2)

m(H)+ma+mb=1.m(H) + m_a + m_b = 1.

Thus, we subdivide the cases (1) and (2) as follows.

(1.a) m(C)=0m(C) = 0 and m(H)=0m(H) = 0 and ma=2m_a = 2 (thus mb=0m_b = 0)

(1.b) m(C)=0m(C) = 0 and m(H)=0m(H) = 0 and ma=1m_a = 1 (thus mb=1m_b = 1)

(1.c) m(C)=0m(C) = 0 and m(H)=0m(H) = 0 and ma=0m_a = 0 (thus mb=2m_b = 2)

(1.d) m(C)=0m(C) = 0 and m(H)=1m(H) = 1 and ma=1m_a = 1 (thus mb=0m_b = 0)

(1.e) m(C)=0m(C) = 0 and m(H)=1m(H) = 1 and ma=0m_a = 0 (thus mb=1m_b = 1)

(1.f) m(C)=0m(C) = 0 and m(H)=2m(H) = 2 (thus ma=0m_a = 0 and mb=0m_b = 0)

(2.a) m(C)=3m(C) = 3 and m(H)=0m(H) = 0 and ma=1m_a = 1 (thus mb=0m_b = 0)

(2.b) m(C)=3m(C) = 3 and m(H)=0m(H) = 0 and ma=0m_a = 0 (thus mb=1m_b = 1)

(2.c) m(C)=3m(C) = 3 and m(H)=1m(H) = 1 (thus ma=0m_a = 0 and mb=0m_b = 0) In the following, we refer again to the names of types of graphs depicted in Figure 4.

In Case (1.a), as mb=0m_b = 0, by the same arguments as in Case (1.a) in the proof of (c), we obtain I2I_2 or I3I_3 as graph GG.

In Case (1.b), if a cross-edge is adjacent to a clique-connecting edge, then we obtain I5I_5. Otherwise, we obtain I4I_4.

In Case (1.c) we necessarily obtain I6I_6.

In Case (1.c), as mb=0m_b = 0, by the same arguments as in Case (1.b) in the proof of (c), we obtain I1I_1 or I2I_2 or I3I_3.

In Case (1.e), if the edge of HH is adjacent to a clique-connecting-edge, then we obtain I5I_5. Otherwise, we obtain I4I_4.

In Case (1.f), as mb=0m_b = 0, by the same arguments as in Case (1.c) in the proof of (c), we obtain I2I_2 or I3I_3.

In Case (2.a) we obtain I4I_4.

In Case (2.b) we obtain I6I_6.

In Case (2.c) we obtain I4I_4 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). □\square

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 B(m)B(m) for 0≤m≤110 \le m \le11, see Table 3. We have implemented these values B(m)B(m) in the OEIS (OEIS Foundation Inc. (2026)) in sequence A363772.

nng(⌊n2⌋)g\left(\left\lfloor\frac{n}{2}\right\rfloor\right)A(n)A(n)∑k=0⌊n/2⌋g(k)2(k2)2k2+n−2k−1n−2k\sum_{k=0}^{\left\lfloor n/2\right\rfloor}g(k)2^{\binom{k}{2}}2^{\frac{k^2+n-2k-1}{n-2k}}∑k=0⌊n/2⌋g(k)2(k2)2(n−2k)k\sum_{k=0}^{\left\lfloor n/2\right\rfloor}g(k)2^{\binom{k}{2}}2^{(n-2k)k}
01111
11111
21122
31233
42489
5292125
642178113
7465343545
81124020043841
91111281533731873
10346764141466362753
11345397117144115112321

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 A(n)A(n)

n\mn \backslash m01234567891011
01
11
21
3101
410201
51020302001
6102050604
710205011013
8102070160
9102060170
1010207021
1110206019
12102070
13102060
1410207
1510206
161020
171020
18102
19102
2010
2110
221
231
B(m)B(m)222366101621365376

Table 3. The number of graphs admitting a strictly matched involution with mm edges (and nn vertices) for m≤11m \le11. The values for 0≤n≤110 \le n \le11 are taken from Table 2, the values for 12≤n≤2312 \le n \le23 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 GG, the following statements are equivalent:

(1) GG admits a strictly matched involution.

(2) G∨K1G \vee K_1 admits a strictly matched involution.

By induction, we get the second form.

Lemma 7.2 (decomposition lemma, version 2: aggregated form) For every graph GG and every n∈Nn \in\mathbb{N}, the following statements are equivalent:

(1) GG admits a strictly matched involution.

(2) G∨KnG \vee K_n 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 n∈Nn \in\mathbb{N} and every subgraph S=(V,E)S=(V,E) of KnK_n, the following statements are equivalent:

  1. The complement S‾\overline{S} of SS admits a strictly matched involution.

  1. Kn−EK_n-E 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 GG admits a strictly matched involution σ\sigma. If we add a new fixed point vv to GG that is connected to every vertex of GG, then the mapping σ′\sigma' with

σ′(w)={σ(w),if w≠v;v,if w=v;\sigma'(w)= \begin{cases} \sigma(w), & \text{if } w\ne v;\\ v, & \text{if } w=v; \end{cases}

is a strictly matched, involutive graph automorphism. This proves the trivial implication (1) ⟹\Longrightarrow (2).

Now assume that G′=G∨K1G'=G\vee K_1 admits a strictly matched involution σ′\sigma'. Let vv be the vertex of K1K_1. If vv is in the fixed point set F1(G′,σ′)F_1(G',\sigma'), then we may obviously delete vv and σ′∣G\sigma'|_G is still strictly matched, well-defined, and involutive. Thus, suppose that

v∈F2(G′,σ′).v\in F_2(G',\sigma').

Let w=σ′(v)w=\sigma'(v). Since vv is connected to every vertex of GG, the vertex ww is connected to every other vertex of G′G' (as σ′\sigma' is a graph automorphism). Thus we may consider ww as a part of the clique, i.e., we may define a map σ\sigma on the vertex set of GG by

σ(x)={σ′(x),if x≠w;w,if x=w.\sigma(x)= \begin{cases} \sigma'(x), & \text{if } x\ne w;\\ w, & \text{if } x=w. \end{cases}

The map σ\sigma is a strictly matched involutive graph automorphism, since σ′\sigma' has the same property on G−wG-w and ww is a fixed point of σ\sigma connected to every other vertex, in particular, to every pair of vertices of orbit 2. This proves the non-trivial implication (2) ⟹\Longrightarrow (1). □

Proof of Lemma 7.2: Applying Lemma 7.1 inductively nn times implies the statement of Lemma 7.2. □

Proof of Lemma 7.3: Since Kn−EK_n-E is isomorphic to S‾∨Kn−∣V∣\overline{S}\vee K_{n-|V|}, the statement of Lemma 7.3 directly follows from Lemma 7.2 when substituting GG by S‾\overline{S} and nn by n−∣V∣n-|V|. □

In the proof of Theorem 3.4 we will also frequently make use of the following obvious lemma.

Lemma 7.4 For every graph GG admitting a strictly matched involution σ\sigma and every edge vwvw of GG with σ(v)=w\sigma(v)=w, i.e., for every matching edge vwvw, we have

dG(v)=dG(w).d_G(v)=d_G(w).

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 nn vertices and (n2)\binom{n}{2} edges is the complete graph on nn vertices, which is a graph admitting a strictly matched involution with k=0k=0 matching edges and a clique of size nn, the assertion follows trivially.

Ad (b): For n≥4n \ge4, there are only two graphs with (n2)−2\binom{n}{2}-2 edges. They can be obtained from the complete graph on nn edges by deleting either two nonadjacent or two adjacent edges. We will prove that these two graphs admit a strictly matched involution.

If nn 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 nn 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 GG be a graph admitting a strictly matched involution with nn vertices, where n≥8n \ge8, and with m=(n2)−4m=\binom{n}{2}-4 edges. By Lemma 7.3, the number of such graphs is the same as the number of graphs SS with 4 edges and without isolated vertices whose complement S‾\overline{S} 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 SiS_i with 4 edges (without isolated vertices) and their complements Si‾\overline{S_i}

It is easy to see that the 6 graph complements S‾1\overline{S}_1, S‾4\overline{S}_4, S‾6\overline{S}_6, S‾7\overline{S}_7, S‾10\overline{S}_{10}, and S‾11\overline{S}_{11} 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 S‾2\overline{S}_2 first. Since none of the edges of S‾2\overline{S}_2 has vertices of equal degree and the vertices of the graph are not a clique, by Lemma 7.4 the graph S‾2\overline{S}_2 cannot admit a strictly matched involution.

  • The same argument applies to S‾3\overline{S}_3.

  • In S‾5\overline{S}_5, by Lemma 7.4 the only possible matching edges would be {1,4}\{1,4\}, {1,5}\{1,5\}, and {4,5}\{4,5\}, 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 S‾5\overline{S}_5.

  • If we assume that S‾8\overline{S}_8 admits a strictly matched involution σ\sigma, 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 {1,6}\{1,6\}, whereas the edge {1,σ(6)}\{1,\sigma(6)\} does not exist, which is a contradiction to the structural theorem (Theorem 2.1).

  • If we assume that S‾9\overline{S}_9 admits a strictly matched involution, by Lemma 7.4 the only possible matching edges are at most two edges on the vertex set {1,4,5,6}\{1,4,5,6\}. 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 SiS_i, 1≤i≤111 \le i \le11, do not have more than 8 vertices. Thus we have proved that, for every n≥8n \ge8,

C(n,(n2)−4)=6,C\left(n,\binom{n}{2}-4\right)=6,

which proves (c).

Remark 7.5 From the proof of Theorem 3.4 (c) we may also deduce the following trivial values: As only S‾11\overline{S}_{11} has 8 vertices, we conclude that

C(7,(72)−4)=5.C\left(7,\binom{7}{2}-4\right)=5.

As there are only two of the graphs S‾i\overline{S}_i that admit a strictly matched involution with more than 6 vertices, we have

C(6,(62)−4)=4;C\left(6,\binom{6}{2}-4\right)=4;

and by similar arguments we conclude

C(5,(52)−4)=3C\left(5,\binom{5}{2}-4\right)=3

and

C(4,(42)−4)=1.C\left(4,\binom{4}{2}-4\right)=1.

Open problems and conjectures

The main open problem arising from this paper is the following.

Problem 8.1 Determine C(n,m)C(n,m) for further values of nn and mm.

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 S1S_1 and S11S_{11} and their complements), some graphs and their complements do not admit a strictly matched involution (e.g., S8S_8 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., S2S_2). Thus the following might be interesting. Problem 8.5 Characterise (or determine the complexity of characterising) the class of graphs GG, for which neither GG nor its complement G‾\overline{G} admits a strictly matched involution.

Problem 8.6 Characterise (or determine the complexity of characterising) the class of graphs GG, for which both GG and its complement G‾\overline{G} admit a strictly matched involution.

Python3 enumeration program

Idea of the Python3 program

For fixed nn and kk, the enumeration program creates a list of graphs admitting a strictly matched involution on nn vertices with respect to some strictly matched involution with kk matching edges according to the structure theorem (Theorem 2.1) in the following way:

(Step 1) Based on a list of all graphs HH on kk vertices, for every such graph HH, we construct a graph with two isomorphic copies of HH, connected by matching edges, and a clique of size n−2kn - 2k.

(Step 2) For every graph GG 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 GG and these pairs of clique-connecting edges.

(Step 3) For every graph GG 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 GG and these pairs of cross edges.

Finally, we iterate over all kk (k∈{0,1,…,⌊n2⌋}k \in\{0, 1, \ldots, \left\lfloor\frac{n}{2} \right\rfloor\}) and apply isomorphism tests to the union of the lists obtained from Step 3 (for all kk) to get the list of all (pairwise nonisomorphic) graphs admitting a strictly matched involution with nn vertices (and separate this list into lists of graphs admitting a strictly matched involution with nn vertices and mm edges for m∈{0,…,(n2)}m \in\{0, \ldots, \binom{n}{2}\}); the number of these graphs is C(n,m)C(n,m)).

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. [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. [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. [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. [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. [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. [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. [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. [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. [9]T. Halverson and M. Reeks. Gelfand models for diagram algebras. Journal of Algebraic Combinatorics, 41:229–255, 2015.
  10. [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. [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. [12]U. Larsson, R. J. Nowakowski, and C. P. Santos. Game comparison through play. Theoretical Computer Science, 725:52–63, 2018a.DOI
  13. [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. [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. [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. [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
  17. [18]J. Quaintance and H. Kwong. Permutations and combinations of colored multisets. Journal of Integer Sequences, 13:12 pp., 2010. Article 10.2.6.
  18. [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
  19. [20]I. Režan. Untersuchungen zur Anzahl von Graphen mit strikt gepaarter Involution. Master thesis, Fern-Universität in Hagen, Germany, 2020.
  20. [21]S. J. Seo and P. J. Slater. Competition parameters of a graph. AKCE International Journal of Graphs and Combinatorics, 4:183–190, 2007.
  21. [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

Paper details

vlnc:W_nvtsqbqv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents