login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A319492 Number of connected non-3-semi-transitively orientable graphs on n vertices. 0

%I #10 Sep 28 2018 10:19:18

%S 0,1,25,929,54953,4879508

%N Number of connected non-3-semi-transitively orientable graphs on n vertices.

%C A graph is k-semi-transitively orientable if it admits an acyclic orientation that avoids shortcuts of length k or less. The notion of a k-semi-transitive orientation refines that of a semi-transitive orientation, which is the case of k equal infinity. For n<9, the number of non-3-semi-transitively orientable graphs is precisely the number of non-semi-transitively orientable graphs, which in turn is the same as the number of non-word-representable graphs. For n=9, there are four 3-semi-transitively orientable graphs which are not semi-transitively orientable.

%H Ozgur Akgun, Ian P. Gent, Sergey Kitaev, Hans Zantema, <a href="https://arxiv.org/abs/1808.01215">Solving computational problems in the theory of word-representable graphs</a>, arXiv:1808.01215 [math.CO], 2018.

%e The wheel graph W_5 is the only connected graph on 6 vertices that is non-3-semi-transitively orientable.

%Y The first four terms are the same as the terms 5 - 8 in A290814.

%K nonn,more

%O 5,3

%A _Sergey Kitaev_, Sep 20 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 08:22 EDT 2024. Contains 371236 sequences. (Running on oeis4.)