cp's OEIS Frontend

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

%I A360839 #39 Mar 15 2023 11:43:42
%S A360839 1,6,32,103,250,220
%N A360839 Number of minimal graphs of twin-width 2 on n unlabeled vertices.
%C A360839 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.
%C A360839 All such graphs are connected, have connected complements, and have no twins. If a graph is counted, so is its complement.
%C A360839 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.
%C A360839 It is known that a(n) >= 1 for any n >= 5, as the n-cycle is always a valid example for n >= 5.
%C A360839 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.
%H A360839 Édouard Bonnet et al., <a href="http://perso.ens-lyon.fr/edouard.bonnet/twinwidth.html">Introduction to Twin-width</a>.
%H A360839 Édouard Bonnet et al., <a href="https://arxiv.org/abs/2004.14789">Twin-width I: tractable FO model checking</a>, arXiv:2004.14789 [cs.DS], 2020-2021.
%H A360839 GraphClasses, <a href="https://www.graphclasses.org/smallgraphs.html">List of Small Graphs</a>.
%e A360839 For n=5, the only case is the 5-cycle C5, thus a(5)=1 is the first term.
%e A360839 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.
%K A360839 nonn,more
%O A360839 5,2
%A A360839 _Alex Meiburg_, Feb 24 2023