This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A319492 Number of connected non-3-semi-transitively orientable graphs on n vertices. 0
 0, 1, 25, 929, 54953, 4879508 (list; graph; refs; listen; history; text; internal format)
 OFFSET 5,3 COMMENTS 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. LINKS Ozgur Akgun, Ian P. Gent, Sergey Kitaev, Hans Zantema, Solving computational problems in the theory of word-representable graphs, arXiv:1808.01215 [math.CO], 2018. EXAMPLE The wheel graph W_5 is the only connected graph on 6 vertices that is non-3-semi-transitively orientable. CROSSREFS The first four terms are the same as the terms 5 - 8 in A290814. Sequence in context: A218589 A264006 A218203 * A290814 A218230 A219060 Adjacent sequences:  A319489 A319490 A319491 * A319493 A319494 A319495 KEYWORD nonn,more AUTHOR Sergey Kitaev, Sep 20 2018 STATUS approved

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

Last modified October 18 13:31 EDT 2019. Contains 328161 sequences. (Running on oeis4.)