A366367 Number of simplicial-free connected simple graphs on n unlabeled vertices.

1, 0, 0, 0, 1, 4, 24, 191, 3094, 95204, 5561965

Offset

0,6

Comments

A simplicial vertex is one whose neighborhood induces a complete graph. A simplicial-free graph has no such vertices.

Links

Table of n, a(n) for n=0..10.

Chı́nh. T Hoàng, Stefan Hougardy, Frédéric Maffray and N.V.R. Mahadev, On simplicial and co-simplicial vertices in graphs, Discrete Applied Mathematics 138, (2004) 117-132.

Andrew M. Steane, Threat, support and dead edges in the Shannon game, arXiv:1210.7985 [math.CO], 2012.

Example

For n=0 the graph with no vertices has no simplicial vertices so a(0)=1.
For n=4 the only case is C4 so a(4)=1.
For n=5 the a(5)=4 solutions are C5 and the graphs obtained by adding to C4 a further vertex adjacent to either 4,3 or 2 of the others, in the latter case without forming a triangle:
    o      o      o
   /|\    /|\    /|\
  o o o  o-o-o  o-o-o
   \|/    \ /    \|/
    o      o      o

Crossrefs

Sequence in context: A001506 A354123 A088815 * A367144 A193854 A199540

Adjacent sequences: A366364 A366365 A366366 * A366368 A366369 A366370

Keyword

nonn,more

Author

Andrew M. Steane, Oct 08 2023

Status

approved