login
A360839
Number of minimal graphs of twin-width 2 on n unlabeled vertices.
0
1, 6, 32, 103, 250, 220
OFFSET
5,2
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.
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.
EXAMPLE
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.
CROSSREFS
Sequence in context: A211918 A288961 A090382 * A102359 A000397 A200765
KEYWORD
nonn,more
AUTHOR
Alex Meiburg, Feb 24 2023
STATUS
approved