|
|
A319492
|
|
Number of connected non-3-semi-transitively orientable graphs on n vertices.
|
|
0
|
|
|
|
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
|
|
|
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.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|