A360839 Number of minimal graphs of twin-width 2 on n unlabeled vertices.

1, 6, 32, 103, 250, 220

Offset: 5

Author

Alex Meiburg, Feb 24 2023

Keywords

• nonn
• more

Comments

a(n) is the number of graphs on n nodes that have twin-width exactly 2, such that deletion of any single vertex would reduce the twin-width. That is, the graphs of twin-width 2 that are minimal under the induced subgraph order.

All such graphs are connected, have connected complements, and have no twins. If a graph is counted, so is its complement.

The only known self-complementary graphs are the 5-cycle and a particular n=8 graph with G6 code "GCpfK{". These are the only two, at least up through n=10. Thus a(5) and a(8) are odd while the rest are even.

It is known that a(n) >= 1 for any n >= 5, as the n-cycle is always a valid example for n >= 5.

The corresponding sequence for twin-width 1 is very simple: 1,0,0,0,... with offset 4, as the 4-vertex path (path of length 3) is the unique minimal graph of twin-width 1. Starting with n=8, there are graphs of twin-width 3; this sequence only counts those of twin-width 2.

Examples

			For n=5, the only case is the 5-cycle C5, thus a(5)=1 is the first term.
For n=6, there are the C6, the S3, and Antenna graphs (by the terminology of GraphClasses.org, see Links), and their complements. Thus a(6)=6.
		

Links

• Édouard Bonnet et al., Introduction to Twin-width.
• Édouard Bonnet et al., Twin-width I: tractable FO model checking, arXiv:2004.14789 [cs.DS], 2020-2021.
• GraphClasses, List of Small Graphs.