A363772 Number of graphs (with n edges) admitting a strictly matched involution.

2, 2, 2, 3, 6, 6, 10, 16, 21, 36

Offset

0,1

Links

Table of n, a(n) for n=0..9.

S. D. Andres, F. Dross, M. A. Huggan, F. Mc Inerney, and R. J. Nowakowski, The complexity of two colouring games, Algorithmica, 85 (2023), 1067-1090.

S. D. Andres, M. Huggan, F. Mc Inerney, and R. J. Nowakowski, The orthogonal colouring game, Theor. Comput. Sci., 795 (2019), 312-325.

S. D. Andres, M. Huggan, F. Mc Inerney, and R. J. Nowakowski, Corrigendum to "The orthogonal colouring game" [Theor. Comput. Sci. 795 (2019) 312-325], Theor. Comput. Sci., 842 (2020), 133-135.

Example

For n=0 the a(0)=2 solutions are the empty graph K0 and the complete graph K1.
For n=1 the a(1)=2 solutions are the complete graph K2 and the union of K2 and K1.
For n=2 the a(2)=2 solutions are 2K2 (the union of two K2) and the union of two K2 and one K1.
For n=3 the a(3)=3 solutions are the complete graph K3, 3K2 (the union of three K2), and the union of three K2 and one K1.
For n=4 the a(4)=6 solutions are the paw (3-pan), the 4-cycle C4, the union of C4 and K1, the union of K2 and K3, 4K2 (the union of four K2), and the union of four K2 and one K1.

Crossrefs

Cf. A363771 (counting by number of vertices instead of number of edges).

Sequence in context: A038715 A293518 A057040 * A096235 A147851 A367088

Adjacent sequences: A363769 A363770 A363771 * A363773 A363774 A363775

Keyword

nonn,hard,more

Author

Stephan Dominique Andres, Jun 21 2023

Status

approved